BZOJ 4033 [HAOI2015]树上染色
有一棵点数为N的树,树边有边权。给你一个在0~N之内的正整数K,你要在这棵树中选择K个点,将其染成黑色,并
将其他的N-K个点染成白色。将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。
问收益最大值是多少。
设dp[i][j]为以i为子树,染j个黑点对全局的贡献
dp[i][j]=dp[i][j-t]+dp[e][t]+cost
cost考虑i的儿子对i的连边的贡献,设边权为ev,儿子为son
cost=t_ev_(k-t)+(size[son]-t)*(n-size[son]-k+t)
特别值得注意的是,该状态设定时就是考虑对全局的贡献,而不是对以i为根的子树的贡献
CODE:
\#include<bits/stdc++.h>
#define ll long long
struct edge{
int to,next;ll v;
}e[5000];
inline ll read(){;
ll x=0,flag=1;//
scanf("%lld",&x);
return x;char c=getchar();
while(!isdigit(c)){if(c=='-')flag*=-1;c=getchar();}
while(isdigit(c)){x=1ll*(x<<3)+1ll*(x<<1)+c-'0';c=getchar();}
return flag*x;
}
int cnt=0,last[4000],size[4000],n,k;
ll dp[2010][2010];
inline void add(int a,int b,ll c){
cnt++;
e[cnt].next=last[a],last[a]=cnt;
e[cnt].to=b,e[cnt].v=c;
}
inline void dfs(int x,int fa){
size[x]=1;
dp[x][1]=dp[x][0]=0;
for(int i=last[x];i;i=e[i].next){
if(e[i].to==fa) continue;
dfs(e[i].to,x);
size[x]+=size[e[i].to];
}
for(int i=last[x];i;i=e[i].next){
if(e[i].to==fa) continue;
for(int j=std::min(k,size[x]);j>=0;--j){
for(int t=0;t<=std::min(j,size[e[i].to]);++t)
if(dp[x][j-t]!=-1){
dp[x][j]=std::max(dp[x][j],dp[x][j-t]+1ll*dp[e[i].to][t]+1ll*e[i].v*t*(k-t)+1ll*e[i].v*(n-k+t-size[e[i].to])*(size[e[i].to]-t));
//printf("%lld\n",+1ll*e[i].v*t*(k-t)+1ll*e[i].v*(n-k+t-size[e[i].to])*(size[e[i].to]-t));
}
}
}
}
int main(){
n=read(),k=read();
for(int i=1;i<=n-1;++i){
int a=read(),b=read(),c=read();
add(a,b,c);
add(b,a,c);
}
memset(dp,-1,sizeof(dp));
dfs(1,0);
printf("%lld",dp[1][k]);
return 0;
}
本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。
本文永久链接: http://www.mayflyyh.com/archives/321