BZOJ4987：Tree （树形DP）

Description

从前有棵树。

找出K个点A1，A2，…，Ak。

使得∑dis(AiAi+1),(1<=i<=K-1)最小。

Input

第一行两个正整数n,k,表示数的顶点数和需要选出的点个数。

接下来n-l行每行3个非负整数x,y,z，表示从存在一条从x到y权值为z的边。

I<=k<=n。

l<x,y<=n

1<=z<=10^5

n <= 3000

Output

一行一个整数，表示最小的距离和。

Sample Input

10 7
1 2 35129
2 3 42976
3 4 24497
2 5 83165
1 6 4748
5 7 38311
4 8 70052
3 9 3561
8 10 80238

Sample Output

184524

思路：求大小为K的连通块的最小遍历距离，最小值显然等于边权之和*2-直径。我们利用这个来DP，用dp[i][j]表示i子树有j个直径的端点(i<=N,j<=2); 如果我i子树有两个直径端点，则当前边不在直径上，如果子树有一个直径端点，则当前边再直径上....其他类似

然后就不难得到方程。注意合并的时候要01像背包一样从大到小，以免一个数用两次。（或者用一个临时变量数组）

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int Laxt[maxn],Next[maxn<<],To[maxn<<],Len[maxn<<],cnt;

int N,K,sz[maxn],dp[maxn][maxn][],ans;

void add(int u,int v,int w){

    Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=w;

}

void dfs(int u,int fa){

    sz[u]=; dp[u][][]=; dp[u][][]=; dp[u][][]=;

    for(int i=Laxt[u];i;i=Next[i]){

        int v=To[i]; if(v==fa) continue;

        dfs(v,u);

        for(int j=sz[u];j>=;j--){

            for(int k=sz[v];k>=;k--){

                dp[u][j+k][]=min(dp[u][j+k][],dp[u][j][]+dp[v][k][]+*Len[i]);

                dp[u][j+k][]=min(dp[u][j+k][],dp[u][j][]+dp[v][k][]+Len[i]);

                dp[u][j+k][]=min(dp[u][j+k][],dp[u][j][]+dp[v][k][]+*Len[i]);

                dp[u][j+k][]=min(dp[u][j+k][],dp[u][j][]+dp[v][k][]+Len[i]);

                dp[u][j+k][]=min(dp[u][j+k][],dp[u][j][]+dp[v][k][]+*Len[i]);

                dp[u][j+k][]=min(dp[u][j+k][],dp[u][j][]+dp[v][k][]+*Len[i]);

            }

        }

        sz[u]+=sz[v];

    }

    ans=min(ans,dp[u][K][]);

}

int main()

{

    int u,v,w;

    scanf("%d%d",&N,&K);

    memset(dp,0x3f,sizeof(dp));

    for(int i=;i<N;i++){

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w); add(v,u,w);

    }

    ans=0x3f3f3f3f;

    dfs(,);

    printf("%d\n",ans);

    return ;

}

秒客网