90分wa第三个点求助!
查看原帖
90分wa第三个点求助!
327069
Lqwq楼主2021/10/13 11:25
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#define inf 0x3f3f3f3f
using namespace std;

long long n,w[150005],tot,head[300010],f[300010][5],rt;
bool vis[300010];

struct lwt
{
	long long to;
	long long next;
}mapp[300010];

void addt(long long from,long long to)
{
	mapp[++tot].to=to;
	mapp[tot].next=head[from];
	head[from]=tot;
}

void dfs(long long u);

int main()
{
	scanf("%d",&n);
	
	long long x,y,z,k;
	for(long long i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld",&x,&k,&y);
		w[x]=k;
		for(long long j=1;j<=y;j++)
		{
			scanf("%lld",&z);
			addt(x,z);
			vis[z]=true;
		}
	}
	for(long long i=1;i<=n;i++)
	{
		if(vis[i]==false)
		{
			rt=i;
			break;
		}
	}
	f[0][0]=inf;
	dfs(rt);
	printf("%lld",min(f[1][0],f[1][1]));
	
	return 0;
}

void dfs(long long u)
{
	long long x=0;
	f[u][0]=w[u];
	for(long long i=head[u];i;i=mapp[i].next)
	{
		long long v=mapp[i].to;
		dfs(v);
		f[u][0]+=min(f[v][0],min(f[v][1],f[v][2]));
		f[u][2]+=min(f[v][0],f[v][1]);
		if((f[x][0]-min(f[x][0],f[x][1]))>(f[v][0]-min(f[v][0],f[v][1])))
		x=v;
	}
	f[u][1]=f[x][0];
	for(long long i=head[u];i;i=mapp[i].next)
	{
		long long v=mapp[i].to;
		if(v==x)
		continue;
		f[u][1]+=min(f[v][0],f[v][1]);
	}
}

谢谢丫

2021/10/13 11:25
加载中...