自动搬运

查看原文

来自洛谷，原作者为

	JK_LOVER 却顾所来径，苍苍横翠微。

搬运于2025-08-24 22:15:05，当前版本为作者最后更新于2020-05-29 20:47:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

写在前面的

在洛谷这么多题中，又找到一群还未开发的题。结合网上的题解，说说自己的看法。地址

题意

在一棵树上，求问从点 $1$ 出发又回到点 $1$ 的最小花费。其中可以选择两个端点跳跃，花费为 $K$ 。但每条边要至少经历 $1$ 次。

分析

• 先考虑没有跳跃的情况：

$$ans=2\times\sum_i^{n-1} W_{e_i}$$

• 因为树上的简单路径有且只有一条。所以我们可以将路径转化为端点来考虑。

$$ans=2\times \sum_i^{n-1}W_{e_i} - \sum_j^{m}W_{e_j}+K\times m $$

• 因为每条路径至少要经历一次，所以我们选取的路径是要不重合的。对于一个树根来考虑。
• 如果子树中端点有偶数个，那么树根一定不在路径上。若有，则不满足每条路径至少经历一次。
• 所以子树端点为奇数时，则这条路径一定包含树根。
• 这样我们就可以写出方程：

$$dp[u][i+j] = \min(dp[u][i+j],dp[u][i]+dp[v][j]+W_{e_i}) \ (j\&1=1) $$$$dp[u][i+j] = \min(dp[u][i+j],dp[u][i]+dp[v][j]+2\times W_{e_i}) \ (j\&1=0) $$

代码就比较简单了。

代码

#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x=0,f=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return f?-x:x;
}
const int N = 1010;
int dp[N][N],n,m,k,ans,size[N],res[N];
vector<int> G[N],W[N];
void dfs(int u,int fa)
{
	size[u] = 1;
	for(int i = 0;i < G[u].size();i++)
	{
		int v = G[u].at(i),w = W[u].at(i);
		if(v == fa) continue;
		dfs(v,u);
		memset(res,0x3f,sizeof(res));
		
		for(int j = 0;j <= size[u];j++)
		{
			for(int k = 0;k <= size[v];k++)
			{
				if(j+k > 2*m) continue;
				if(k&1)
				{
					res[j+k] = min(res[j+k],dp[u][j]+dp[v][k]+w);
					res[j+k+1] = min(res[j+k+1],dp[u][j]+dp[v][k]+w);
				}
				else 
				{
					res[j+k] = min(res[j+k],dp[u][j]+dp[v][k]+2*w);
					res[j+k+1] = min(res[j+k+1],dp[u][j]+dp[v][k]+2*w); 
				}
			}
		}
		size[u] += size[v];
		for(int j = 0;j <= size[u];j++) dp[u][j] = res[j];
		
	}
}
int main()
{
	int T = read();
	while(T--)
	{	
		memset(dp,0,sizeof(dp));
		ans = 0;
		n = read();m = read();k = read();
		for(int i = 1;i <= n;i++) G[i].clear(),W[i].clear();
		for(int i = 1;i < n;i++)
		{
			int a = read(),b = read(),c = read();
			G[a].push_back(b);
			W[a].push_back(c);
			G[b].push_back(a);
			W[b].push_back(c);	
			ans += c+c;
		} 
		dfs(1,0);
		for(int i = 0;i <= min(2*m,n);i += 2)
		{
			ans = min(ans,dp[1][i] + (i/2)*k);
		}
		printf("%d\n",ans);
	}

}