求助:WA on #3
查看原帖
求助:WA on #3
735235
hmwzd1314楼主2024/7/10 19:37
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k[1509],dp[1509][3],ok[1509],root;
vector<int>e[1509];
bool jntm[1509];
struct node
{
	int v1,v2;	
};
void dfs(int x,int rt)
{
	int siz=e[x].size();
	dp[x][1]=k[x];
	dp[x][0]=0;
	int nb=0x3f3f3f3f;
	for(int i=0;i<siz;i++)
	{
		int v=e[x][i];
		if(v==rt)continue;
		dfs(v,x);
		dp[x][1]+=min(min(dp[v][1],dp[v][0]),dp[v][2]);
		dp[x][0]+=min(dp[v][0],dp[v][1]);
		nb=min(nb,dp[v][1]-dp[v][0]);
		dp[x][2]+=min(dp[v][1],dp[v][0]);
	}
	if(nb!=0x3f3f3f3f)dp[x][0]+=max(nb,0ll);
	if(!ok[x])dp[x][0]=0x3f3f3f3f;
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		cin>>k[i]>>ok[i];
		for(int j=0;j<ok[i];j++)
		{
			int pos;
			cin>>pos;
			e[x].push_back(pos);
			jntm[pos]=1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!jntm[i])
		{
			root=i;
			break;
		}
	}
	dfs(root,0);
	cout<<min(dp[root][1],dp[root][0]);
	return 0;
}
2024/7/10 19:37
加载中...