首页 > 代码库 > BZOJ 4033: [HAOI2015]树上染色
BZOJ 4033: [HAOI2015]树上染色
Description
一棵树，选择\(k\)个黑点，令黑点间距离+白点间距离和最大.\(n\leqslant 2\times 10^3\)
Solution
树形DP.
每次暴力合并子节点信息..
这样做其实是\(n^2\)的...因为两个点被合并一定是在LCA处..这样合并次数就变成的树中的点对个数
Code
/************************************************************** Problem: 4033 User: BeiYu Language: C++ Result: Accepted Time:432 ms Memory:34192 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; #define mpr make_pair#define x first#define y second typedef long long LL;typedef pair<int,int> pr;const int N = 2050; inline int in(int x=0,char ch=getchar(),int v=1) { while(ch>‘9‘||ch<‘0‘) v=ch==‘-‘?-1:v,ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();return x*v; } int n,k;vector<pr> g[N];LL f[N][N],sz[N],tmp[N]; void AddEdge(int fr,int to,int dis) { g[fr].push_back(mpr(to,dis)); }void DP(int u,int fa) { sz[u]=1; for(int t=0,v;t<(int)g[u].size();t++) if((v=g[u][t].x)!=fa){ DP(v,u); for(int i=0;i<=sz[u]+sz[v];i++) tmp[i]=0; for(int i=0;i<=sz[u];i++) { for(int j=0;j<=sz[v];j++) { if(i+j>k) break; tmp[i+j]=max(tmp[i+j],f[u][i]+f[v][j]+g[u][t].y*(j*(k-j)+(sz[v]-j)*(n-k-(sz[v]-j)))); } }sz[u]+=sz[v]; for(int i=0;i<=sz[u];i++) f[u][i]=tmp[i]; }/* cout<<"------"<<endl; cout<<u<<" "<<fa<<" "<<sz[u]<<endl; for(int i=0;i<=sz[u];i++) cout<<f[u][i]<<" ";cout<<endl;*/} int main() { n=in(),k=in(); for(int i=1;i<n;i++) { int u=in(),v=in(),d=in(); AddEdge(u,v,d),AddEdge(v,u,d); } DP(1,1); printf("%lld\n",f[1][k]); return 0;}
BZOJ 4033: [HAOI2015]树上染色
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。