[bzoj4987]Tree

Tree bzoj-4987

题目大意：给定一颗n个点的有边权的树，选出k个点，使得：$\sum\limits_{i=1}^{k-1}dis_idis_j$最小。

注释：$1\le n\le 3000$。

想法：

我们考虑答案的可能形态：

肯定是一颗大小为k的联通子树这是显然的。

那么我们考虑如果把答案的$dis_{k-1}dis_k$加上，就是每条边都算两遍。

现在把最后一项去掉了，我们当然要好好利用，所以我们的答案一定是所有边权*2-直径长度。

这样就可以$dp$了：

状态：$dp[i][j][l]$在$i$的子树中，选了$j$个点，其中有$l$个点所谓直径的端点。

转移就用背包的转移即可。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 3010

using namespace std;

int head[N],to[N<<1],len[N<<1],next[N<<1],cnt,si[N],f[N][N][3];

inline void add(int x,int y,int z)

{

	to[++cnt]=y,len[cnt]=z,next[cnt]=head[x],head[x]=cnt;

}

void dfs(int x,int fa)

{

	int i,j,k,l,m;

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

	for(i=head[x];i;i=next[i])

	{

		if(to[i]==fa) continue;

		dfs(to[i],x);

		for(j=si[x]-1;~j;j--)

			for(k=si[to[i]]-1;~k;k--)

				for(l=2;~l;l--)

					for(m=l;~m;m--)

						f[x][j+k+1][l]=min(f[x][j+k+1][l],f[x][j][l-m]+f[to[i]][k][m]+len[i]*(2-(m&1)));

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

	}

}

int main()

{

	int n,k,x,y,z,ans=1<<30;

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

	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][k-1][j]);

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

	return 0;

}

小结：好题！

巴特西

[bzoj4987]Tree_树形dp

最新文章

热门文章