90求调,卡第三个了
查看原帖
90求调,卡第三个了
1147417
Ashkadira楼主2024/8/25 15:22
using namespace std;
long long n,t=0,root=0;
struct node
{
	int to,next;
}e[5000];//i点放置一个保安,可以把他的父亲和儿子都监管到 
long long a[1550],head[1550],ru[1550],fa[1550];
long long dp[1550][3];//dp[][0]表示自己放保安,[1]表示儿子放保安,[2]表示父亲放保安 
void add(int x,int y)
{
	t++;
	e[t].to=y;
	e[t].next=head[x];
	head[x]=t;
}
void dfs(int x)
{
	dp[x][0]=a[x];
	dp[x][1]=dp[x][2]=0;
	int cnt=0;
	long long cha=0x3f3f3f3f;
	for(int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa[x])continue;
		dfs(v);
		dp[x][2]+=min(dp[v][1],dp[v][0]);
		dp[x][0]+=min(min(dp[v][1],dp[v][0]),dp[v][2]);
		if(dp[v][0]<dp[v][1])cnt++;
        else cha=min(cha,dp[v][0]-dp[v][1]);
		dp[x][1]+=min(dp[v][1],dp[v][0]);
	}
	if(cnt==0)dp[x][1]+=cha; 
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x,m;
		cin>>x>>a[x]>>m;
		for(int j=1;j<=m;j++)
		{
			int y;
			cin>>y;
			fa[y]=x;
			ru[y]++;
			add(x,y);
			add(y,x);
		}
	}
	//for(int i=1;i<=n;i++)if(ru[i]==0)root=i;
	dfs(1);
	cout<<min(dp[1][1],dp[1][0]);
	return 0;
}
2024/8/25 15:22
加载中...