自动搬运

查看原文

来自洛谷，原作者为

	lolte 昆卡昆卡，嘶哈嘶哈嘶哈

搬运于2025-08-24 21:44:15，当前版本为作者最后更新于2018-10-29 13:48:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

蒟蒻$lolte$的题解

这题不难想到要用到拓扑排序，但我不像其他两位题解一样需要平均分配。

我用拓扑关系来递推每个点到牛奶流量。挤奶机为1，其余为 $from$ 的流量之和。

特别的，当一个点的出度大于1时，这个点后面的点绝不是混合器，即非答案。

当一个点的流量为牛奶总流量时，这个点是答案。

代码如下

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9') {
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch<='9'&&ch>='0') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int maxn=100010;
int n,id[maxn],od[maxn],to[maxn],q[maxn],liu[maxn],l=1,r=0,tot=0;
bool ji[maxn];
int main(){
	memset(id,0,sizeof(id));
	memset(od,0,sizeof(od));
	n=read();
	for (int i=1;i<n;++i) {
		int a,b;
		a=read();
		b=read();
		to[a]=b;
		++od[a];//出度+1 
		++id[b];//入度+1 
	}
	for (int i=1;i<=n;++i) {
		if (!id[i]) {
			q[++r]=i;//加入队列 
			liu[i]=1;//挤奶器流量为1 
			++tot;//统计牛奶总流量 
			ji[i]=1;//标记为挤奶器 
		}
	}
	while (l<=r) {
		//拓扑流程 
		int u=q[l];
		if (od[u]>1) {
			//入度>1，后面直接不管 
			liu[to[u]]=0;
			++l;
			continue;
		}
		liu[to[u]]+=liu[u];//累加流量 
		--id[to[u]];
		if (!id[to[u]]) {//加点 
			q[++r]=to[u];
		}
		++l;
	}
	r=0;
	for (int i=1;i<=n;++i) {
		if (ji[i]) continue;//挤奶器不管 
		if (liu[i]==tot) q[++r]=i;//统计答案 
	}
	for (int i=1;i<=r;++i) printf("%d\n",q[i]);
}

_ (:з」∠) ---