BZOJ 4033 T1
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4033
题目大意
有一棵点数为 N 的树，树边有边权。给你一个在 0~ N 之内的正整数 K ，你要在这棵树中选择 K个点，将其染成黑色，并将其他的N-K个点染成白色 。 将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。
题解
F[i][k]表示以i为根节点的子树在子树中选择k个节点时，子树中每条边对最终答案的贡献。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #define LL long long using namespace std; const int Maxn=2000; struct Edge{ int v,nxt; LL w; Edge(){} Edge(int v0,int n0,LL w0){ v=v0; nxt=n0; w=w0; } }; Edge e[Maxn*2+5]; int head[Maxn+5]; int nume; inline void addEdge(int u,int v,LL w){ e[++nume]=Edge(v,head[u],w); head[u]=nume; e[++nume]=Edge(u,head[v],w); head[v]=nume; } LL F[Maxn+5][Maxn+5]; LL tmp[Maxn+5]; int siz[Maxn+5]; int n,m; void DP(int x,int fa,LL w){ siz[x]=1; for (int i=head[x];i;i=e[i].nxt){ int v=e[i].v;LL w=e[i].w; if (v==fa) continue; DP(v,x,w); for (int j=0;j<=min(m,siz[x]);j++) tmp[j]=F[x][j]; for (int p1=0;p1<=min(m,siz[x]);p1++) for (int p2=0;p2<=min(m,siz[v]);p2++){ if (p1+p2<=m) F[x][p1+p2]=max(F[x][p1+p2],tmp[p1]+F[v][p2]); } siz[x]+=siz[v]; } for (int down=0;down<=min(m,siz[x]);down++) F[x][down]+=w*(LL)(down*(m-down)+(siz[x]-down)*(n-siz[x]-(m-down))); } inline void solve(){ nume=0; memset(head,0,sizeof(head)); for (int i=1;i<n;i++){ int x,y; LL w; scanf("%d%d%lld",&x,&y,&w); addEdge(x,y,w); } memset(F,0,sizeof(F)); DP(1,0,0); printf("%lld\n",F[1][m]); } int main(){ freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m)!=EOF){ solve(); } return 0; } |
原文链接：BZOJ 4033 T1
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!