自动搬运

查看原文

来自洛谷，原作者为

	阿丑 ArrTue

搬运于2025-08-24 22:21:15，当前版本为作者最后更新于2021-01-21 20:09:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

非常明显的一题环套树，注意到本题条件：

如果还完债后还有剩余， $B$ 也会自己留着。（$B$ 的行为对于任意一个人适用）

即，每个人欠的钱，就是他还给债主的钱 （废话）。请注意。

思路：

1. 首先去掉所有不被其他人欠钱的人，因为这种人必须由政府出钱。之后可以直接把他欠的钱给出去，再删除这个节点。

2. 步骤 $1$ 后环套树就只剩下了环，一一枚举计算即可。

第一步

对于所有不被其他人欠钱的人，由于他所欠的钱一定由政府出，直接将他所欠的钱累加进答案 $ans$，再将他的钱还给债主，然后就可以删除他和他对应的边了。

而若此时的债主不被其他人欠钱了，也可以这么处理。代码如下：

//ind 表示入度，val 表示所欠的钱，now 表示手里有的钱，fa 表示债主
for(int x=1; x<=n; ++x)
	if(ind[x]==0) {
		for(int u=x; ind[u]==0; u=fa[u]) {
			ans+=max(val[u]-now[u], 0);	//累加 
			--ind[fa[u]];	//删边 
			now[fa[u]]+=val[u];	//给钱
 
			ind[u]=-1;	//标记u，防止此后被重复计算 
		}
	}

第二步

执行完第一步后，可以发现图只剩了下了入度 $\ge 1$ 的节点。由于原图是环套树森林，故此时只剩下了很多个环。

对于环上的任意一个节点 $su$，设他的债主为 $u$，则对于 $u$ 的还钱，有两种情况：

1. $su$ 先还给了 $u$ 共 $val[su]$ 的钱，政府再给 $u$ 剩下的钱（如果需要），凑够 $val[u]$ 后还钱。此时政府支出 $val[u]-(val[su]+now[u])$ 的钱（如果是负数，则不用支出，下文同理）。

2. $su$ 还没给钱，政府就给了 $u$ 所需的钱，支出 $val[u]-now[u]$ 的钱。

由于 $val[su]>0$，故第一种情况一定更赚，即政府至少要给出 $\sum val[u]-(val[su]+now[u])$。

但是，所有人都不会自动给钱，必须由政府给其中一个人钱才会触发某人的第一种情况，随后即可触发所有人的第一种情况，故只需给一人 $val[u]-now[u]$，可以想到记录两种情况差值的最小值。

（若有人在第一步中已经有了足够还债主的钱，则可以看做政府给了 $0$ 元钱。此时差值为 $0$，一定是最小值。）

代码如下：

if(ind[x]>0) {
	int dans=INF;
	for(int u=fa[x], su=x; ind[u]>0; su=u, u=fa[u]) {
		int c1=max(val[u]-val[su]-now[u], 0), c2=max(val[u]-now[u], 0);
		ans+=c1;
		if(dans>c2-c1) dans=c2-c1;	//记录最小值
		ind[u]=0;	//标记
	}
	ans+=dans;
}

然后就结束了（甚至图都没存，码量挺小），完整代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200000+30, INF=2000000000+10;
int n, fa[MAXN], val[MAXN], ind[MAXN], now[MAXN];
void init() {
	scanf("%d", &n);
	for(int x=1; x<=n; ++x)
		scanf("%d%d", &fa[x], &val[x]), ++ind[fa[x]];
	return;
}
void solve() {
	int ans=0;
	for(int x=1; x<=n; ++x)
		if(ind[x]==0) {
			for(int u=x; ind[u]==0; u=fa[u]) {
				ans+=max(val[u]-now[u], 0);
				--ind[fa[u]];
				now[fa[u]]+=val[u];
				ind[u]=-1;
			}
		}
	for(int x=1; x<=n; ++x)
		if(ind[x]>0) {
			int dans=INF;
			for(int u=fa[x], su=x; ind[u]>0; su=u, u=fa[u]) {
				int c1=max(val[u]-val[su]-now[u], 0), c2=max(val[u]-now[u], 0);
				ans+=c1;
				if(dans>c2-c1) dans=c2-c1;
				ind[u]=0;
			}
			ans+=dans;
		}
	printf("%d\n", ans);
	return;
}
int main() {
	init();
	solve();
	return 0;
}

本蒟蒻的第一篇题解，见谅 $QAQ$。