BZOJ 4033 [HAOI2015]树上染色

作者: MayFlyyh 分类: DP 发布时间: 2018-08-16 15:45 ė 6 没有评论

有一棵点数为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

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部