Mayflyyh
Mayflyyh
MayFlyyh's Blog
BZOJ 4987 Tree

从前有棵树。

找出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<x,y<=n
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<bits/stdc++.h>
#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;
}
本文链接:http://www.mayflyyh.com/archives/343
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      DP      BZOJ 4987 Tree
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

MayFlyyh's Blog

BZOJ 4987 Tree
从前有棵树。 找出K个点A1,A2,…,Ak。 使得$∑dis(A_i,A_i+1),(1<=i<=K-1)$最小。 第一行两个正整数n,k,表示数的顶点数和需要选出的点个数。 接下来n-l行每行3个…
扫描二维码继续阅读
2018-09-18