90分WA on #3求助!
查看原帖
90分WA on #3求助!
1060212
Saturation楼主2024/8/19 08:38
#include<bits/stdc++.h>
using namespace std;
const int N=6100;
int n;
int e[N],h[N],ne[N],idx;
int a[N];
int dp[N][3]; 
int fa[N];
int d[N];
int root;
int rd[N];
int ans=0x3f3f3f3f;
void add(int x,int y)
{
	e[++idx]=y;
	ne[idx]=h[x];
	h[x]=idx;
}
void df(int u,int dep)
{
	d[u]=dep;
	for(int i=h[u];~i;i=ne[i])
	{
		int v=e[i];
		if(!d[v])
		{
			fa[v]=u;
			df(v,dep+1);
		}
	}
}
void dfs(int u)
{
	dp[u][0]=a[u];
	bool flag=0;
	int tmp=0x3f3f3f3f;
	for(int i=h[u];~i;i=ne[i])
	{
		int v=e[i];
		if(fa[u]!=v)
		{
			dfs(v);
			dp[u][0]+=min(dp[v][0],min(dp[v][1],dp[v][2]));
			dp[u][2]+=min(dp[v][1],dp[v][0]); 
			if(dp[v][0]<dp[v][1])
			{
				flag=1;
			}
			else
			{
				tmp=min(tmp,dp[v][0]-dp[v][1]);
			}
			dp[u][1]+=min(dp[v][1],dp[v][0]);
		}
	}
	if(!flag)
	{
		dp[u][1]+=tmp;
	}
}
int in()
{
	int ans=0,ff=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar())
	{
		if(c=='-')
		{
			ff*=-1;
		}
	}
	for(;isdigit(c);c=getchar())
	{
		ans=ans*10+c-'0';
	}
	return ans*ff;
}
void out(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>10)
	{
		out(x/10);
	}
	putchar(x%10+'0');
}
int main()
{
	memset(h,-1,sizeof h);
	n=in();
	for(int i=1;i<=n;i++)
	{
		int x=in();
		a[x]=in();
		int m=in();
		for(int j=1;j<=m;j++)
		{
			int y=in();
			rd[y]++;
			add(x,y);
			add(y,x);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!rd[i])
		{
			root=i;
			break;
		}
	}
	df(root,1);
	dfs(root);
	out(min(dp[root][0],dp[root][1]));
	return 0;
}

2024/8/19 08:38
加载中...