BZOJ 4987 Tree

作者: MayFlyyh 分类: DP 发布时间: 2018-09-18 23:01 ė 6 没有评论

> 从前有棵树。

> 找出K个点A1,A2,…,Ak。

> 使得∑dis(A_i,A_i+1),(1<=i<=K-1)最小。 > 第一行两个正整数n,k,表示数的顶点数和需要选出的点个数。
> 接下来n-l行每行3个非负整数x,y,z,表示从存在一条从x到y权值为z的边。
> 1<=k<=n。 > l 1<=z<=10^5 > n <= 3000 --- 好题是好题。。完全没看懂题意 由于是∑dis(A_i,A_i+1),那必定是一个联通块。(选中的点都挨在一起) 再联通块中,肯定有一条链上的边可以只经过一遍,剩下的边则要经过两遍。 现在要找出这条链的两条端点。设DP[i][j][k]表示在i为根的子树下选了j个点(包括i),有k个端点在子树内。 ``` ll tmp=dp[x][j+1][p]+dp[e[i].to][k][l-p]+e[i].v*2; if(l-p==1) tmp-=e[i].v; dp[x][j+k+1][l]=std::min(dp[x][j+k+1][l],tmp); ``` 如果有2个或者0个端点已经在遍历过的子树了话,那说明现在i到儿子的边必不在链上。 当一个端点在内部,那说明还有一个端点在外部,说明这个边在链上,只走一遍 ``` #include
#define ll long long
const int N = 3010;
int last[N],n,cnt,K;
ll dp[N][N][3],ans=1e18;
int size[N];
struct edge{
int next,to,v;
}e[N<<1]; void add(int x,int y,int z){ cnt++; e[cnt].next=last[x],last[x]=cnt; e[cnt].v=z;e[cnt].to=y; } void dfs(int x,int fa){ dp[x][1][0]=dp[x][1][1]=0; for(int i=last[x];i;i=e[i].next){ if(e[i].to==fa) continue; dfs(e[i].to,x); for(int j=size[x];j+1;--j){ for(int k=size[e[i].to];k+1;--k){ for(int l=2;l+1;--l){ for(int p=l;p+1;--p){ ll tmp=dp[x][j+1][p]+dp[e[i].to][k][l-p]+e[i].v*2; if(l-p==1) tmp-=e[i].v; dp[x][j+k+1][l]=std::min(dp[x][j+k+1][l],tmp); } } } } size[x]+=size[e[i].to]; } size[x]++; ans=std::min(ans,dp[x][K][2]); ans=std::min(ans,dp[x][K][0]); ans=std::min(ans,dp[x][K][1]); } int main(){ scanf("%d %d",&n,&K); for(int i=1;i<=n-1;++i){ int x,y,z; scanf("%d %d %d",&x,&y,&z); add(x,y,z),add(y,x,z); } memset(dp,0x3f,sizeof(dp)); dfs(1,0); printf("%lld",ans); return 0; } ```

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/343

发表评论

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

Ɣ回顶部