题解 P6486 【[COCI2010-2011#4] DUGOVI】

· · 题解

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

如果还完债后还有剩余， 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 的还钱，有两种情况：

由于 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。