江湖救急
查看原帖
江湖救急
335094
Lucifero楼主2020/9/12 21:30
#include<bits/stdc++.h>
using namespace std;
int k[1440],son[1440],bro[1440],boss[1440],f[1440][3],n,ans;
void Tree_dp(int u)
{
	int i;
	f[u][0]=0,f[u][1]=k[u],f[u][2]=0;
	int cost=INT_MAX;
	for(i=son[u];i!=0;i=bro[i])
	{
		Tree_dp(i);
		f[u][0]+=min(f[i][1],f[i][2]);
		f[u][1]+=min(min(f[i][0],f[i][1]),f[i][2]);
		f[u][2]+=min(f[i][1],f[i][2]);
		cost=min(cost,f[i][1]-min(f[i][1],f[i][2]));
	}
	f[u][2]+=cost;
}
int main()
{
	int num,m,dot,i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&num,&k[i],&m);
		for(j=1;j<=m;j++)
		{
			scanf("%d",&dot);
			bro[dot]=son[num];son[num]=dot;
			boss[dot]=num;
		}
	}
	for(i=1;i<=n;i++)
		if (boss[i]==0)
		{
			Tree_dp(i);
			ans+=min(min(f[i][0],f[i][1]),f[i][2]);
		}
	printf("%d",ans);
}
2020/9/12 21:30
加载中...