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

Solution

贴一下神仙$beginend$的题解qwq

显然最优情况一定是原树的一棵大小为k的连通子树，然后直径上的边系数是1，其余边的系数是2。
那么我们可以进行树形dp，设f[i,j,0/1/2]表示以i为根的子树选了j个点，且直径的端点已经选了0/1/2个的最优方案。

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define N (3009)

 using namespace std;

 struct Edge{int to,next,len;}edge[N<<];

 int n,m,u,v,l,ans,INF,size[N],f[N][N][],tmp[N][];

 int head[N],num_edge;

 void add(int u,int v,int l)

 {

     edge[++num_edge].to=v;

     edge[num_edge].len=l;

     edge[num_edge].next=head[u];

     head[u]=num_edge;

 }

 void Min(int &x,int y){x=min(x,y);}

 void Dfs(int x,int fa)

 {

     size[x]=;

     for (int i=;i<=n;i++)

         for (int j=;j<=;j++)

             f[x][i][j]=INF;

     f[x][][]=f[x][][]=f[x][][]=;

     for (int i=head[x]; i; i=edge[i].next)

         if (edge[i].to!=fa)

         {

             Dfs(edge[i].to,x);

             for (int j=; j<=size[x]+size[edge[i].to]; ++j)

                 tmp[j][]=tmp[j][]=tmp[j][]=INF;

             for (int j=; j<=size[x]; ++j)

                 for (int k=; k<=size[edge[i].to]; ++k)

                 {

                     int to=edge[i].to,len=edge[i].len;

                     Min(tmp[j+k][],f[x][j][]+f[to][k][]+len*);

                     Min(tmp[j+k][],f[x][j][]+f[to][k][]+len*);

                     Min(tmp[j+k][],f[x][j][]+f[to][k][]+len);

                     Min(tmp[j+k][],f[x][j][]+f[to][k][]+len);

                     Min(tmp[j+k][],f[x][j][]+f[to][k][]+len*);

                     Min(tmp[j+k][],f[x][j][]+f[to][k][]+len*);

                 }

             size[x]+=size[edge[i].to];

             for (int j=; j<=size[x]; ++j)

                 for (int k=; k<=; ++k)

                     f[x][j][k]=min(f[x][j][k],tmp[j][k]);

         }

     ans=min(ans,f[x][m][]);

 }

 int main()

 {

     memset(&INF,0x3f,sizeof(INF));

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

     for (int i=; i<=n-; ++i)

     {

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

         add(u,v,l); add(v,u,l);

     }

     ans=INF; Dfs(,);

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

 }

秒客网