【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

Sol

首先显然这些点是树中的一个联通子块。这个联通子块也是一棵树，而这个联通子块内最优的安排顺序就是让直径只走一遍，其他的边都走两遍。所以我们的treedp是需要围绕直径展开的。我们不妨枚举一个子树内包含了多少个直径上的端点（0,1,2），然后树形背包合并。

设$f[i][j][k]$表示以i为根的子树中，有j个选定的点，这些点中直径的端点有k个。那么在合并答案的时候，如果子节点子树的$k=0$，那么说明子节点子树内的边全都不是直径，所以当前根节点到这个子节点的边长就要经过两次；如果子节点子树的$k=1$，那么说明子节点子树内有直径的一部分，所以当前根节点到这个子节点的边长也是直径，只用经过一次；如果$k=2$，那么说明整个直径都在子节点子树内，所以当前根节点到这个子节点的边长需要经过两次。之后我们只需要枚举子树中关键点的个数，枚举两个子树中的k，再加上当前这条边的贡献，就能够完成转移了。

$f[x][a+b+1][c]=min(f[x][a+b+1][c],f[x][a][c-d]+f[to[i]][b][d]+len[i]*(2-(d&1))); $

其中a,b枚举的是子节点关键点的点数，c表示根节点的k,d表示子节点的k，转移的时候枚举这些变量即可。

Code

#include <bits/stdc++.h>

using namespace std;

int hed[3005],to[6005],len[6005],nex[6005],cnt,siz[3005],f[3005][3005][3],n,m,x,y,z,ans=2147483647;

void add(int x,int y,int z){to[++cnt]=y,len[cnt]=z,nex[cnt]=hed[x],hed[x]=cnt;}

void dfs(int x,int fa)

{

    siz[x]=1,f[x][0][0]=f[x][0][1]=0;

    for(int i=hed[x];i;i=nex[i]) if(to[i]!=fa)

    {

        dfs(to[i],x);

        for(int a=siz[x]-1;~a;a--) for(int b=siz[to[i]]-1;~b;b--) for(int c=2;~c;c--) for(int d=c;~d;d--)

            f[x][a+b+1][c]=min(f[x][a+b+1][c],f[x][a][c-d]+f[to[i]][b][d]+len[i]*(2-(d&1)));

        siz[x]+=siz[to[i]];

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<n;i++) scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);

    memset(f,0x3f,sizeof(f));dfs(1,0);

    for(int i=1;i<=n;i++) for(int j=0;j<=2;j++) ans=min(ans,f[i][m-1][j]);

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

}

秒客网