洛谷P3177/HAOI2015 树上染色

@Pelom  November 11, 2019

题意

有一棵点数为$N$的树,树边有边权。给你一个在$0 \sim N$之内的正整数$K$,你要在这棵树中选择$K$个点,将其染成黑色,并将其他 的$N-K$个点染成白色
将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少

数据范围:$0 \le k \le n \le 2000$

题解

因为计算答案时需要对整颗树考虑,而一条边的贡献为$$一侧的黑/白色点数 \times 另一侧的黑/白色点数 \times 边权$$
因此用$f[u][i]$表示以$u$为根的子树中选择$i$个黑色节点的最大贡献
易得状态转移方程$$f[u][i]=\max_{j=0}^{\min(i,siz[v])} f[u][j]+f[v][k-j]+val$$其中$val$为这条边的贡献

注:

  • 非法情况:$u$中总子树大小不足$j-k$
  • 枚举边界:不能超过子树大小
  • 枚举顺序:枚举$i$需倒序(类似$01$背包);枚举$j$需先转移$j=0$的情况

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=2000+10;
int n,m,u,v,w;
int cnt;
int head[N],siz[N];
LL dp[N][N];
struct edge{
    int nxt,to,w;
} e[N<<1];
inline void add(int u,int v,int w){
    e[++cnt]=(edge){head[u],v,w};
    head[u]=cnt;
}
void dfs(int u,int f){
    siz[u]=1;
    dp[u][0]=dp[u][1]=0;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==f)
            continue;
        dfs(v,u);
        siz[u]+=siz[v];
        for(int j=min(m,siz[u]);~j;j--)
            for(int k=0;k<=min(j,siz[v]);k++){
                if(dp[u][j-k]==-1)
                    continue;
                dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]+1ll*k*(m-k)*e[i].w+1ll*(siz[v]-k)*(n-m-siz[v]+k)*e[i].w);
            }
    }
}
int main(){
    memset(dp,-1,sizeof(dp));
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1,0);
    printf("%lld",dp[1][m]);
    return 0;
}

添加新评论

  1. 膜拜巨巨

    Reply