中石油训练赛 - Flow Finder(树上模拟)

题目链接：点击查看

题目大意：给出一棵树，模拟网络流的过程，每个节点代表的是通过该节点的流量，虚拟源点连向每个叶子节点，根节点作为超级汇点，每条边的流向是流向其父节点，有一些节点的流量没有给出，现在问是否存在着唯一的一种赋值方案，使得每个节点的赋值合法且唯一

题目分析：因为源点与叶子节点相连，所以我们的当务之急是需要将所有的叶子节点进行合法的赋值，然后 dfs 自底向上检查一下每个节点是否合法且唯一即可，那么我们该如何给叶子节点赋值呢

因为整棵树的每个节点都是一个互相限制的过程，同理叶子节点也会被其祖先节点的流量所限制，所以我们在给叶子节点赋值时，并不关心那些流量未知的节点，对于每个叶子结点 i 只需要记录一下 fa[ i ] 代表的是 i 的第一个已经有确定流量的祖先节点，根据这个祖先的流量来判断能否给当前叶子节点赋值即可

代码：
 

#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;
     
typedef long long LL;
     
typedef unsigned long long ull;
     
const int inf=0x3f3f3f3f;
   
const int N=3e5+100;

vector<int>node1[N],node2[N];

int fa[N];

LL val[N],sub[N];//sub数组用来实时每个点的流量

void dfs1(int u)
{
	for(auto v:node1[u])
	{
		if(val[u])
			fa[v]=u;
		else
			fa[v]=fa[u];
		dfs1(v);
	}
}

void dfs2(int u)
{
	LL temp=val[u];
	if(node1[u].size())
		val[u]=0;
	for(auto v:node1[u])
	{
		dfs2(v);
		val[u]+=val[v];
	}
	if(val[u]==0||temp>0&&val[u]!=temp)
	{
		puts("impossible");
		exit(0);
	}
}

int main()
{
#ifndef ONLINE_JUDGE
//  freopen("data.in.txt","r",stdin);
//  freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);
	int n;
	scanf("%d",&n);
	for(int i=2;i<=n;i++)
	{
		int fa;
		scanf("%d",&fa);
		node1[fa].push_back(i);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",val+i);
		sub[i]=val[i];
	}
	dfs1(1);
	for(int i=1;i<=n;i++)
	{
		sub[fa[i]]-=val[i];//更新一下每个节点的流量
		if(node1[i].empty()&&!val[i])//未赋值的叶子结点 
			node2[fa[i]].push_back(i);
	}
	for(int i=1;i<=n;i++)
		if(node2[i].size())//有流量的节点 
		{
			if(node2[i].size()==1)//如果只有一个叶子节点，那么赋值为sub[i]
				val[node2[i].front()]=sub[i];
			else if(node2[i].size()==sub[i])//如果有sub[i]个叶子结点，每个节点赋值为1
			{
				for(auto v:node2[i])
					val[v]=1;
			}
		}
	dfs2(1);//自底向上检查
	for(int i=1;i<=n;i++)
		printf("%lld\n",val[i]);















   return 0;
}

 

本文地址：https://blog.csdn.net/qq_45458915/article/details/108577329