头像

秦淮岸灯火阑珊

yxc粉丝后援会。 QQ:862062587




离线:6小时前



算法解析

首先我们得有这道题目的铺垫

其实就是模板的铺垫

然后我们再来看这道题目。

对于图论的题目,一定要分析好几个要素

  1. 这是什么图
  2. 这个图的特点是什么
  3. 题目要我求什么

显然这道题目是:

  1. 无向图
  2. 图有双向边,而且有的点可能不连通
  3. 最短时间

在这里的话,看到最短这两个字,不难想到是最短路

但是这里题目却在问,整个送信流程的最短时间。

不是一个点收到信就是送完整个流程了。

而是最晚的一个点收到信,说明送完了整个流程。

因此我们只需要找到最晚这个点收到信的最短时间就可。

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N=2200;
int edge[N],ver[N],Next[N],head[N],tot;
int n,m,k,dis[N],vis[N];
inline void add_edge(int a,int b,int c)//建造图
{
    edge[++tot]=b;
    ver[tot]=c;
    Next[tot]=head[a];
    head[a]=tot;
}
inline void spfa(int st)//标准的SPFA算法
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(st);
    dis[st]=0;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        vis[now]=false;
        for(int i=head[now]; i; i=Next[i])
        {
            int y=edge[i];
            if (dis[now]+ver[i]<dis[y])//三角形更新这个点的最短时间
            {
                dis[y]=dis[now]+ver[i];
                if (!vis[y])//这个更新点不在队列之中
                {
                    vis[y]=true;
                    q.push(y);
                }
            }
        }
    }
}
inline void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add_edge(a,b,c);
        add_edge(b,a,c);//构造无向图
    }
    spfa(1);
    int ans=0;
    for(int i=1; i<=n; i++)//找到这个最晚的点的最短时间
        ans=max(ans,dis[i]);
    printf("%d\n",ans==1061109567?-1:ans);//判断是否有点不能够达到
}
signed main()
{
    init();
    return 0;
}


活动打卡代码 AcWing 1128. 信使

#include <bits/stdc++.h>
using namespace std;
const int N=2200;
int edge[N],ver[N],Next[N],head[N],tot;
int n,m,k,dis[N],vis[N];
inline void add_edge(int a,int b,int c)
{
    edge[++tot]=b;
    ver[tot]=c;
    Next[tot]=head[a];
    head[a]=tot;
}
inline void spfa(int st)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(st);
    dis[st]=0;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        vis[now]=false;
        for(int i=head[now]; i; i=Next[i])
        {
            int y=edge[i];
            if (dis[now]+ver[i]<dis[y])
            {
                dis[y]=dis[now]+ver[i];
                if (!vis[y])
                {
                    vis[y]=true;
                    q.push(y);
                }
            }
        }
    }
}
inline void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add_edge(a,b,c);
        add_edge(b,a,c);
    }
    spfa(1);
    int ans=0;
    for(int i=1; i<=n; i++)
        ans=max(ans,dis[i]);
    printf("%d\n",ans==1061109567?-1:ans);
}
signed main()
{
    init();
    return 0;
}


活动打卡代码 AcWing 1129. 热浪

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+20;
int n,m,edge[N],Next[N],head[N],ver[N],st,ed,tot,vis[N],dis[N];
inline void add_edge(int a,int b,int c)
{
    edge[++tot]=b;
    ver[tot]=c;
    Next[tot]=head[a];
    head[a]=tot;
}
inline void spfa(int st)
{
    queue<int> q;
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    q.push(st);
    dis[st]=0;
    //上面都是初始化
    while(!q.empty())
    {
        int now=q.front();
        vis[now]=false;
        q.pop();
        for(int i=head[now]; i; i=Next[i])//遍历当前点可以抵达的点
        {
            int y=edge[i];
            if (dis[y]>dis[now]+ver[i])//这里是三角形
            {
                dis[y]=dis[now]+ver[i];//ver[i]表示now和y之间的边
                if (!vis[y])//如果本点已经在队列中,无需再加入一次
                {
                    q.push(y);
                    vis[y]=true;
                }
            }
        }
    }
}
inline void init()
{
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add_edge(a,b,c);//这里是添加边
        add_edge(b,a,c);//本题是无向图,有双向边
    }
    spfa(st);//选择起点
    printf("%d\n",dis[ed]);//最终答案
}
signed main()
{
    init();
    return 0;
}

作者:秦淮岸灯火阑珊
链接:https://www.acwing.com/solution/content/28596/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



算法解析

首先分析本题目的框架:一张无向图

再看本题的求两点之间的最短路径

那么这是一道非常常规的模板题目:

单源最短路径

具体的算法解析,大家可以看我的博客

Hint:本题我采用SPFA解决本题

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+20;
int n,m,edge[N],Next[N],head[N],ver[N],st,ed,tot,vis[N],dis[N];
inline void add_edge(int a,int b,int c)
{
    edge[++tot]=b;
    ver[tot]=c;
    Next[tot]=head[a];
    head[a]=tot;
}
inline void spfa(int st)
{
    queue<int> q;
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    q.push(st);
    dis[st]=0;
    //上面都是初始化
    while(!q.empty())
    {
        int now=q.front();
        vis[now]=false;
        q.pop();
        for(int i=head[now]; i; i=Next[i])//遍历当前点可以抵达的点
        {
            int y=edge[i];
            if (dis[y]>dis[now]+ver[i])//这里是三角形
            {
                dis[y]=dis[now]+ver[i];//ver[i]表示now和y之间的边
                if (!vis[y])//如果本点已经在队列中,无需再加入一次
                {
                    q.push(y);
                    vis[y]=true;
                }
            }
        }
    }
}
inline void init()
{
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add_edge(a,b,c);//这里是添加边
        add_edge(b,a,c);//本题是无向图,有双向边
    }
    spfa(st);//选择起点
    printf("%d\n",dis[ed]);//最终答案
}
signed main()
{
    init();
    return 0;
}


新鲜事 原文

加油啊!不能在高一就放弃OI!!!


活动打卡代码 AcWing 104. 货仓选址

#include <bits/stdc++.h>
using namespace std;
const int N=100100;
int a[N],n,i,ans,sum;
int main()
{
    cin>>n;
    for (i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    int sm=a[n/2+1];
    for (i=1;i<=n;i++)
        ans=ans+abs(a[i]-sm);
    cout<<ans;
    return 0;
}



更好的阅读体验

题目描述

题目链接

有一棵点数为 $N$ 的树,树边有边权。

给你一个在 $0 \sim N$ 之内的正整数 $K$,你要在这棵树中选择 $K$ 个点,将其染成黑色,并将其他的 $N-K$ 个点染成白色。

将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。

问收益最大值是多少!

输入格式

第一行两个整数 $N,K$。

接下来 $N-1$ 行每行三个正整数 $fr,to,dis$,表示该树中存在一条长度为 $dis$ 的边 $(fr,to)$。

输入保证所有点之间是联通的。

输出格式

输出一个正整数,表示收益的最大值。

数据范围

$1 \le N \le 2000$,
$0 \le K \le N$

输入样例:

5 2
1 2 3
1 5 1
2 3 1
2 4 2

输出样例:

17

样例解释

将点 $1,2$ 染黑就能获得最大收益。

解题报告

题意理解

原题很清晰,没法简析了。

探索算法

有一说一,第一眼看到这道题目,博主是真的没有认为这道题目的是一个树形DP。

但是,染色的题目,加上最值问题的要求,还是和树形DP联系很大。

那么我们为什么很难看出来呢?可能是因为我太菜了

因为我们的关注点,是一个点,它所提供的贡献。

而不是一条边,所提供的贡献

其实这也是一个难想&常见的思路。

对于树上的题目,求贡献,不是点,就是边至少提高组范畴是这样的

那么如果说,我们按照边来思考的话,这道题目的转移方程还是很有意思的。

算法解析

类似于状态压缩动态规划,树形DP的题目,状态设计是极为重要的一步。

那么如何设计状态呢?

既然上面,我们说了,要按照边来算贡献,那么我们就先来分析边,是如何提供贡献的?

对于一条边而言,他可以提供的贡献,来自于两个节点之间的路径有它,也就是经过它:

  1. 左右两边黑色节点提供的。(自己子树内的黑色节点 $ \times $ 子树外黑色节点。
  2. 左右两边白色节点提供的。(自己子树内的白色节点 $ \times $ 子树外白色节点。

那么此时我们需要确定状态了

$
f[x][i] 表示节点x它到父亲节点的这条边,他的子树有i个染黑节点,此时提供的最大贡献
$

那么对于一个节点他有多少个染黑节点呢?

不知道?

那么枚举吧。

于是本题成了一个树形背包。

每个节点他的子树有多少个黑色节点(体积),然后算出这条边对答案的贡献(价值)

black_sum=s*(k-s)
white_sum=(Size[y]-s)*((n-Size[y])-(k-s)) 

$s$为当前节点他的子树有多少个染成黑色的节点

$k$为题目给出的有k个节点染成黑色

$Size[y]$表示当前节点他的子树一共有多少个节点

因此本题就这么愉快的解决了,在这里默认,树形背包DP大家都会吧。。。

如果不会的话,可以参照Acwing我曾经的背包DP的讲义。

参考代码

//My English is poor.The Code maybe have some grammer problems.
//To have a better Font display in Acwing.com,I must choose English.
#include <bits/stdc++.h>
using namespace std;
const int N=2100;
int n,k,head[N<<1],edge[N<<1],Next[N<<1],tot,Size[N];
long long f[N][N],ver[N<<1];
inline void add_edge(int a,int b,int c)
{
    edge[++tot]=b;
    ver[tot]=c;
    Next[tot]=head[a];
    head[a]=tot;
}
void tree_DP(int x,int fa)
{
    Size[x]=1;
    memset(f[x],-1,sizeof(f[x]));
    f[x][0]=f[x][1]=0;
    for(int i=head[x]; i; i=Next[i])//visit its sons
    {
        int y=edge[i];
        if (y==fa)//its father
            continue;//can't visit its father node
        tree_DP(y,x);//visit the son
        Size[x]+=Size[y];//count the Size of the tree
    }
    //Next part is the DP whose kind is knapsack.
    for(int i=head[x]; i; i=Next[i])
    {
        int y=edge[i];
        if (y==fa)//its father
            continue;//can't visit its father node
        for(int j=min(k,Size[x]); j>=0; j--)//choose black nodes whose number is j
        {
            for(int s=0; s<=min(j,Size[y]); s++)
                if (~f[x][j-s])
                {
                    long long black_sum=s*(k-s);//balck pairs
                    long long white_sum=(Size[y]-s)*((n-Size[y])-(k-s));//white pairs
                    f[x][j]=max(f[x][j],f[x][j-s]+f[y][s]+(black_sum+white_sum)*ver[i]);
                }
        }
    }
}
inline void init()
{
    scanf("%d%d",&n,&k);
    for(int i=1; i<n; i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add_edge(a,b,c);
        add_edge(b,a,c);
    }
    tree_DP(1,0);
    printf("%lld\n",f[1][k]);
}
signed main()
{
    init();
    return 0;
}



更好的阅读体验

谢谢 @Yimingli 找到这篇博文的bug

题目描述

题目链接

一棵二叉树可以按照如下规则表示成一个由 $0、1、2$ 组成的字符序列,我们称之为 “二叉树序列 $S$”:

$S=
\begin{cases}
0 \ \ \ \ \ \ \ \ \ \ 表示该树没有子节点 \newline
1S_1 \ \ \ \ \ \ 表示该树有一个子节点,S_1 为其子树的二叉树序列 \newline
2S_1S_2 \ \ 表示该树有两个子节点,S_1 和 S_2 分别表示其两个子树的二叉树序列
\end{cases}$

例如,下图所表示的二叉树可以用二叉树序列 $S=21200110$ 来表示。

123

你的任务是要对一棵二叉树的节点进行染色。

每个节点可以被染成红色、绿色或蓝色。

并且,一个节点与其子节点的颜色必须不同,如果该节点有两个子节点,那么这两个子节点的颜色也必须不相同。

给定一棵二叉树的二叉树序列,请求出这棵树中最多和最少有多少个点能够被染成绿色。

输入格式

仅有一行,表示一个二叉树序列。

输出格式

只有一行,包含两个数,依次表示最多和最少有多少个点能够被染成绿色。

数据范围

输入序列长度不超过 $5 \times 10^5$。

输入样例:

1122002010

输出样例:

5 2

解题报告

题意理解

每一个节点可以染三种颜色,红黄绿三种,要求父子节点颜色不同,而且左右儿子之间的颜色也要不同,问有多少个节点可以染色为绿色

探求算法

这是一棵

这棵树父子节点之前存在一定的限制关系

题目要求最值计数

根据上面的这些分析,我们不难得出本题需要用树形DP

算法分析

既然本题要用动态规划,那么我们得严格按照,以下顺序求解本题。

  1. 如何设计状态
  2. 状态如何转移

首先,我们来设计状态。

状态的属性必然是,可以染绿色的节点最多是多少。

接着,根据树形DP最常见的状态设计为:

一个节点,及其子树再满足条件的情况下,答案是多少?

所以我们不难设计出:

$$
f[i]为i及其子树,满足染色条件下,可以染成绿色的节点,最多为多少。
$$

这是初级的状态设计,我们还需要通过在分析状态转移的过程中,明确如何完善状态的设计。


接下来,设计状态转移。

分析题目的限制条件,来约束状态转移,使其满足不重复不遗漏。

接下来罗列一下约束条件:

  1. 父与子,节点颜色不同
  2. 左右儿子,两者之间,颜色不同

那么此时我们发现,如果还是初级的状态设计,是没有办法转移的。

因为我们并不知道每个节点的染色情况,那么也无法转移了。

所以我们需要优化状态设计

$$
f[i][0/1/2]表示节点i染色为红,黄,绿,在他和他的子树都满足染色条件下,染成绿色节点最多为多少。
$$

这样,我们就彻底完成了状态设计,那么接下来开始状态转移。

如果说:

$$
a表示左儿子的染色,son_a为左儿子序号 \\
b表示右儿子的染色,son_b为右儿子序号 \\
now表示当前节点的染色,i为当前节点序号
$$

那么显然
$$
a \neq b \neq now\\
$$

f[x][i]=max(f[son_a][a]+f[son_b][b],f[son_a][b]+f[son_b][a]);
g[x][i]=min(g[son_a][a]+g[son_b][b],g[son_a][b]+g[son_b][a]);
//f[son_a][a]为左儿子选择颜色a,f[son_b][b]为右儿子选择颜色b
//f[son_a][b]为左儿子选择颜色b,f[son_b][a]为右儿子选择颜色a
//在这里a,b的定义不同于上面,指的是两种颜色,而且满足a,b不是当前节点的颜色
//f[x][i]为当前节点x选择颜色为i的绿色节点最大值,g[x][i]为最小值

如果说只有一个儿子节点,状态转移方程有所不同,但是和上面思路一样,具体可以直接看代码。

参考代码

//My English is poor.The Code maybe have some grammer problems.
//To have a better Font display in Acwing.com,I must choose English.
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+20;
char s[N];
int tot,tree[N][3],f[N][3],g[N][3],Size[N];
void dfs(int root)//Build the Tree
{
    Size[root]=s[root]-'0';//count the number of sons
    if (s[root]>='1')//left son
    {
        tree[root][0]=++tot;
        dfs(tot);
    }
    if (s[root]=='2')//right son
    {
        tree[root][1]=++tot;
        dfs(tot);
    }
}
void tree_DP(int x)
{
    if (Size[x]==0)//The node is a leaf node
    {
        f[x][2]=g[x][2]=1;
        return ;
    }
    for(int i=0; i<Size[x]; i++)//son
        tree_DP(tree[x][i]);
    for(int i=0; i<=2; i++)//color
    {
        int a=(i+1)%3,b=(i+2)%3;//other colors
        int son_a=tree[x][0],son_b=tree[x][1];//other sons
        if (Size[x]==1)//only a son
        {  

            f[x][i]=max(f[son_a][a],f[son_a][b]);
            g[x][i]=min(g[son_a][a],g[son_a][b]);
        }
        if (Size[x]==2)//two sons
        {
            f[x][i]=max(f[son_a][a]+f[son_b][b],f[son_a][b]+f[son_b][a]);
            g[x][i]=min(g[son_a][a]+g[son_b][b],g[son_a][b]+g[son_b][a]);
        }
        if (i==2)//the now node chooses the green color
            f[x][i]++,g[x][i]++;
        // printf("%d %d %d\n",x,f[x][i],g[x][i]);
    }
}
inline void out()//Output
{
    int ans_Min=1e9,ans_Max=0;
    for(int i=0; i<=2; i++)
    {
        ans_Min=min(ans_Min,g[1][i]);
        ans_Max=max(ans_Max,f[1][i]);
    }
    printf("%d %d\n",ans_Max,ans_Min);
}
inline void init()//Input
{
    scanf("%s",s+1);
    tot=1;
    dfs(1);
}
signed main()
{
    init();
    tree_DP(1);
    out();
    return 0;
}


新鲜事 原文

刷完十道树形dp的水题了,可以开始水水博文了!



题目描述

题目链接

一棵二叉树可以按照如下规则表示成一个由 $0、1、2$ 组成的字符序列,我们称之为 “二叉树序列 $S$”:

$S=
\begin{cases}
0 \ \ \ \ \ \ \ \ \ \ 表示该树没有子节点 \newline
1S_1 \ \ \ \ \ \ 表示该树有一个子节点,S_1 为其子树的二叉树序列 \newline
2S_1S_2 \ \ 表示该树有两个子节点,S_1 和 S_2 分别表示其两个子树的二叉树序列
\end{cases}$

例如,下图所表示的二叉树可以用二叉树序列 $S=21200110$ 来表示。

123

你的任务是要对一棵二叉树的节点进行染色。

每个节点可以被染成红色、绿色或蓝色。

并且,一个节点与其子节点的颜色必须不同,如果该节点有两个子节点,那么这两个子节点的颜色也必须不相同。

给定一棵二叉树的二叉树序列,请求出这棵树中最多和最少有多少个点能够被染成绿色。

输入格式

仅有一行,表示一个二叉树序列。

输出格式

只有一行,包含两个数,依次表示最多和最少有多少个点能够被染成绿色。

数据范围

输入序列长度不超过 $5 \times 10^5$。

输入样例:

1122002010

输出样例:

5 2

解题报告

题意理解

每一个节点可以染三种颜色,红黄绿三种,要求父子节点颜色不同,而且左右儿子之间的颜色也要不同,问有多少个节点可以染色为绿色

探求算法

这是一棵

这棵树父子节点之前存在一定的限制关系

题目要求最值计数

根据上面的这些分析,我们不难得出本题需要用树形DP

算法分析

既然本题要用动态规划,那么我们得严格按照,以下顺序求解本题。

  1. 如何设计状态
  2. 状态如何转移

首先,我们来设计状态。

状态的属性必然是,可以染绿色的节点最多是多少。

接着,根据树形DP最常见的状态设计为:

一个节点,及其子树再满足条件的情况下,答案是多少?

所以我们不难设计出:

$$
f[i]为i及其子树,满足染色条件下,可以染成绿色的节点,最多为多少。
$$

这是初级的状态设计,我们还需要通过在分析状态转移的过程中,明确如何完善状态的设计。


接下来,设计状态转移。

分析题目的限制条件,来约束状态转移,使其满足不重复不遗漏。

接下来罗列一下约束条件:

  1. 父与子,节点颜色不同
  2. 左右儿子,两者之间,颜色不同

那么此时我们发现,如果还是初级的状态设计,是没有办法转移的。

因为我们并不知道每个节点的染色情况,那么也无法转移了。

所以我们需要优化状态设计

$$
f[i][0/1/2]表示节点i染色为红,黄,绿,在他和他的子树都满足染色条件下,染成绿色节点最多为多少。
$$

这样,我们就彻底完成了状态设计,那么接下来开始状态转移。

如果说:

$$
a表示左儿子的染色,son_a为左儿子序号 \\
b表示右儿子的染色,son_b为右儿子序号 \\
now表示当前节点的染色,i为当前节点序号
$$

那么显然
$$
a \neq b \neq now\\
$$

f[x][i]=max(f[son_a][a]+f[son_b][b],f[son_a][b]+f[son_b][a]);
g[x][i]=min(g[son_a][a]+g[son_b][b],g[son_a][b]+g[son_b][a]);
//f[son_a][a]为左儿子选择颜色a,f[son_b][b]为右儿子选择颜色b
//f[son_a][b]为左儿子选择颜色b,f[son_b][a]为右儿子选择颜色a
//在这里a,b的定义不同于上面,指的是两种颜色,而且满足a,b不是当前节点的颜色
//f[x][i]为当前节点x选择颜色为i的绿色节点最大值,g[x][i]为最小值

如果说只有一个儿子节点,状态转移方程有所不同,但是和上面思路一样,具体可以直接看代码。

参考代码

//My English is poor.The Code maybe have some grammer problems.
//To have a better Font display in Acwing.com,I must choose English.
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+20;
char s[N];
int tot,tree[N][3],f[N][3],g[N][3],Size[N];
void dfs(int root)//Build the Tree
{
    Size[root]=s[root]-'0';//count the number of sons
    if (s[root]>='1')//left son
    {
        tree[root][0]=++tot;
        dfs(tot);
    }
    if (s[root]=='2')//right son
    {
        tree[root][1]=++tot;
        dfs(tot);
    }
}
void tree_DP(int x)
{
    if (Size[x]==0)//The node is a leaf node
    {
        f[x][2]=g[x][2]=1;
        return ;
    }
    for(int i=0; i<Size[x]; i++)//son
        tree_DP(tree[x][i]);
    for(int i=0; i<=2; i++)//color
    {
        int a=(i+1)%3,b=(i+2)%3;//other colors
        int son_a=tree[x][0],son_b=tree[x][1];//other sons
        if (Size[x]==1)//only a son
        {  

            f[x][i]=max(f[son_a][a],f[son_a][b]);
            g[x][i]=min(g[son_a][a],g[son_a][b]);
        }
        if (Size[x]==2)//two sons
        {
            f[x][i]=max(f[son_a][a]+f[son_b][b],f[son_a][b]+f[son_b][a]);
            g[x][i]=min(g[son_a][a]+g[son_b][b],g[son_a][b]+g[son_b][a]);
        }
        if (i==2)//the now node chooses the green color
            f[x][i]++,g[x][i]++;
        // printf("%d %d %d\n",x,f[x][i],g[x][i]);
    }
}
inline void out()//Output
{
    int ans_Min=1e9,ans_Max=0;
    for(int i=0; i<=2; i++)
    {
        ans_Min=min(ans_Min,g[1][i]);
        ans_Max=max(ans_Max,f[1][i]);
    }
    printf("%d %d\n",ans_Max,ans_Min);
}
inline void init()//Input
{
    scanf("%s",s+1);
    tot=1;
    dfs(1);
}
signed main()
{
    init();
    tree_DP(1);
    out();
    return 0;
}

更好的阅读体验

题目描述

题目链接

有一棵点数为 $N$ 的树,树边有边权。

给你一个在 $0 \sim N$ 之内的正整数 $K$,你要在这棵树中选择 $K$ 个点,将其染成黑色,并将其他的 $N-K$ 个点染成白色。

将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。

问收益最大值是多少!

输入格式

第一行两个整数 $N,K$。

接下来 $N-1$ 行每行三个正整数 $fr,to,dis$,表示该树中存在一条长度为 $dis$ 的边 $(fr,to)$。

输入保证所有点之间是联通的。

输出格式

输出一个正整数,表示收益的最大值。

数据范围

$1 \le N \le 2000$,
$0 \le K \le N$

输入样例:

5 2
1 2 3
1 5 1
2 3 1
2 4 2

输出样例:

17

样例解释

将点 $1,2$ 染黑就能获得最大收益。

解题报告

题意理解

原题很清晰,没法简析了。

探索算法

有一说一,第一眼看到这道题目,博主是真的没有认为这道题目的是一个树形DP。

但是,染色的题目,加上最值问题的要求,还是和树形DP联系很大。

那么我们为什么很难看出来呢?可能是因为我太菜了

因为我们的关注点,是一个点,它所提供的贡献。

而不是一条边,所提供的贡献

其实这也是一个难想&常见的思路。

对于树上的题目,求贡献,不是点,就是边至少提高组范畴是这样的

那么如果说,我们按照边来思考的话,这道题目的转移方程还是很有意思的。

算法解析

类似于状态压缩动态规划,树形DP的题目,状态设计是极为重要的一步。

那么如何设计状态呢?

既然上面,我们说了,要按照边来算贡献,那么我们就先来分析边,是如何提供贡献的?

对于一条边而言,他可以提供的贡献,来自于两个节点之间的路径有它,也就是经过它:

  1. 左右两边黑色节点提供的。(自己子树内的黑色节点 $ \times $ 子树外黑色节点。
  2. 左右两边白色节点提供的。(自己子树内的白色节点 $ \times $ 子树外白色节点。

那么此时我们需要确定状态了

$
f[x][i] 表示节点x它到父亲节点的这条边,他的子树有i个染黑节点,此时提供的最大贡献
$

那么对于一个节点他有多少个染黑节点呢?

不知道?

那么枚举吧。

于是本题成了一个树形背包。

每个节点他的子树有多少个黑色节点(体积),然后算出这条边对答案的贡献(价值)

black_sum=s*(k-s)
white_sum=(Size[y]-s)*((n-Size[y])-(k-s)) 

$s$为当前节点他的子树有多少个染成黑色的节点

$k$为题目给出的有k个节点染成黑色

$Size[y]$表示当前节点他的子树一共有多少个节点

因此本题就这么愉快的解决了,在这里默认,树形背包DP大家都会吧。。。

如果不会的话,可以参照Acwing我曾经的背包DP的讲义。

参考代码

//My English is poor.The Code maybe have some grammer problems.
//To have a better Font display in Acwing.com,I must choose English.
#include <bits/stdc++.h>
using namespace std;
const int N=2100;
int n,k,head[N<<1],edge[N<<1],Next[N<<1],tot,Size[N];
long long f[N][N],ver[N<<1];
inline void add_edge(int a,int b,int c)
{
    edge[++tot]=b;
    ver[tot]=c;
    Next[tot]=head[a];
    head[a]=tot;
}
void tree_DP(int x,int fa)
{
    Size[x]=1;
    memset(f[x],-1,sizeof(f[x]));
    f[x][0]=f[x][1]=0;
    for(int i=head[x]; i; i=Next[i])//visit its sons
    {
        int y=edge[i];
        if (y==fa)//its father
            continue;//can't visit its father node
        tree_DP(y,x);//visit the son
        Size[x]+=Size[y];//count the Size of the tree
    }
    //Next part is the DP whose kind is knapsack.
    for(int i=head[x]; i; i=Next[i])
    {
        int y=edge[i];
        if (y==fa)//its father
            continue;//can't visit its father node
        for(int j=min(k,Size[x]); j>=0; j--)//choose black nodes whose number is j
        {
            for(int s=0; s<=min(j,Size[y]); s++)
                if (~f[x][j-s])
                {
                    long long black_sum=s*(k-s);//balck pairs
                    long long white_sum=(Size[y]-s)*((n-Size[y])-(k-s));//white pairs
                    f[x][j]=max(f[x][j],f[x][j-s]+f[y][s]+(black_sum+white_sum)*ver[i]);
                }
        }
    }
}
inline void init()
{
    scanf("%d%d",&n,&k);
    for(int i=1; i<n; i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add_edge(a,b,c);
        add_edge(b,a,c);
    }
    tree_DP(1,0);
    printf("%lld\n",f[1][k]);
}
signed main()
{
    init();
    return 0;
}