• 欢迎光临~

【BZOJ4987】Tree(树形dp)

开发技术 开发技术 2022-10-28 次浏览

题意:给你一棵 (n) 个节点的树找出 (k) 个不同的点 (a_1,a_2,cdots,a_k)
使得 (sumlimits_{i=1}^{k-1} dis(a_i,a_{i+1})) 最小。

首先有个容易想到的性质:这 (k) 个点一定是相邻的,那么选 (k) 个点可以看成选 (k-1) 条相连的边。

但关键是我们不是要算一个环的长度,而是一条路径的长度,也就是说不用算从终点再走回到起点的距离,事情就变得麻烦起来。

用树形 dp 求解:设 (dp(i,j,0/1/2)) 表示在 (i) 子树中,选出 (j) 条边的方案数。

其中第 (3) 维是 (0) 表示这条路径的两个端点都在根节点 (i) 上;第 (3) 维是 (1) 表示这条路径的两个端点一个在根节点 (i) 上,另一个在 (i) 的子树内;第 (3) 维是 (2) 表示这条路径的两个端点都在 (i) 的子树内,但是这条路径经过 (i)

那么答案就是 (minlimits_{i=1}^n dp(i,k-1,0/1))

然后转移也比较明显,主要是这个时间复杂度的证明。

证法一:

设对于某一个点 (u),以 (u) 为根的子树大小为 (s)(u) 的儿子的子树大小分别为 (s_1,s_2,cdots,s_m)

那么在 (u) 节点的时间是:

[begin{aligned} &s_1+s_1*s_2+(s_1+s_2)s_3+(s_1+s_2+s_3)s_4+cdots+left(sum_{i=1}^{m-1}s_iright)s_m\ approx&s_1*s_2+(s_1+s_2)s_3+(s_1+s_2+s_3)s_4+cdots+left(sum_{i=1}^{m-1}s_iright)s_m\ <&2left(s_1*s_2+(s_1+s_2)s_3+(s_1+s_2+s_3)s_4+cdots+left(sum_{i=1}^{m-1}s_iright)s_mright)\ =&s_1(s_2+s_3+cdots+s_m)+s_2(s_1+s_3+s_4+cdots+s_m)+s_3(s_1+s_2+s_4+cdots+s_m)\ =&s_1(s-s_1-1)+s_2(s-s_2-1)+s_3(s-s_3-1)+cdots+s_m(s-s_m-1)\ =&s(s_1+cdots+s_m)-(s_1^2+s_2^2+cdots-s_m^2)-(s_1+s_2+cdots+s_m) <&s(s_1+cdots+s_m)-(s_1^2+s_2^2+cdots-s_m^2)\ =&s(s-1)-(s_1^2+s_2^2+cdots-s_m^2)\ <&s^2-s_1^2-s_2^2-cdots-s_m^2 end{aligned}]

然后每两层相消,最后总时间复杂度就是根所代表的子树的大小的平方,即 (O(n^2))

证法二:

dp 的实质可以看做枚举树中的点对 ((u,v)),然后当且仅当存在某一个 (root),使得 (u)(v) 分别在 (root) 的两个儿子的子树中。显然,对于每一个点对 ((u,v)),有且仅有一个 (root=operatorname{lca}(u,v))。所以总时间复杂度是 (O(n^2))

代码如下:

#include<bits/stdc++.h>

#define N 3010
#define ll long long
#define INF 0x7fffffff

using namespace std;

int n,k,size[N];
int cnt,head[N],nxt[N<<1],to[N<<1];
ll w[N<<1],dp[N][N][3];
//dp[0]:根进根出
//dp[1]:根进子树内出
//dp[2]:子树内进子树内出(经过根) 

void adde(int u,int v,ll wi)
{
	to[++cnt]=v;
	w[cnt]=wi;
	nxt[cnt]=head[u];
	head[u]=cnt;
}

void dfs(int u,int fa)
{
	size[u]=1;
	dp[u][0][0]=dp[u][0][1]=0;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		dfs(v,u);
		for(int j=size[u]-1;j>=0;j--)
		{
			for(int k=size[v]-1;k>=0;k--)
			{
				dp[u][j+k+1][0]=min(dp[u][j+k+1][0],dp[u][j][0]+dp[v][k][0]+w[i]*2);
				dp[u][j+k+1][1]=min(dp[u][j+k+1][1],min(dp[u][j][0]+dp[v][k][1]+w[i],dp[u][j][1]+dp[v][k][0]+w[i]*2));
				dp[u][j+k+1][2]=min(dp[u][j+k+1][2],min(dp[u][j][0]+dp[v][k][2]+w[i]*2,min(dp[u][j][1]+dp[v][k][1]+w[i],dp[u][j][2]+dp[v][k][0]+w[i]*2)));
			}
		}
		size[u]+=size[v];
	}
}

int main()
{
	memset(dp,127,sizeof(dp));
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++)
	{
		int u,v;ll w;
		scanf("%d%d%lld",&u,&v,&w);
		adde(u,v,w),adde(v,u,w);
	}
	dfs(1,0);
	ll ans=INF;
	for(int i=1;i<=n;i++)
		ans=min(ans,min(dp[i][k-1][1],dp[i][k-1][2]));
	printf("%lldn",ans);
	return 0;
}
程序员灯塔
转载请注明原文链接:【BZOJ4987】Tree(树形dp)
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com