为什么我把根从一改到二就对了啊啊啊
查看原帖
为什么我把根从一改到二就对了啊啊啊
573963
wbh20090611楼主2024/8/27 15:36

WA

AC code:

#include<bits/stdc++.h>
using namespace std;
vector <int> e[6006];
int n, a[6006], d[6006], dp[6006][3], id, k;
//dp[i][0] 代表父亲控制 
//dp[i][1] 代表儿子控制 
//dp[i][2] 代表自己控制 
void dfs(int x, int fa)
{
	if (e[x].size() == 1 && x != 2)
	{
		dp[x][2] = a[x];
		dp[x][1] = 0x3f3f3f3f;
		return;
	}
	int sum = INT_MAX, cnt = 0;
	for (auto i : e[x])
	{
		if (i == fa)
			continue;
		dfs(i, x);
		dp[x][0] += min(dp[i][2], dp[i][1]);
		if (dp[i][2] <= dp[i][1])
		{
			dp[x][1] += dp[i][2];
			cnt++;
		}
		else
		{
			sum = min(sum, dp[i][2] - dp[i][1]);
			dp[x][1] += dp[i][1];
		}
		dp[x][2] += min({dp[i][1], dp[i][0], dp[i][2]});
	}
	if (cnt == 0)
		dp[x][1] += sum;
	dp[x][2] += a[x]; 
}
int main()
{
    cin >> n;
	for (int i = 1, u, v; i <= n; i++)
	{
		scanf("%d", &id);
		scanf("%d%d", a + id, &k);
		for (int i = 1; i <= k; i++)
		{
			scanf("%d", &v);
			e[id].push_back(v);
			e[v].push_back(id);
		}
	}
	dfs(2, 0); // <- 改成 1 就错了
	cout << min({dp[2][1], dp[2][2], dp[2][0]});
}
2024/8/27 15:36
加载中...