看似在搬luogu文章实则是在分享涩图吗？！

题解：P6486 [COCI 2010/2011 #4] DUGOVI

• 本题解与其它大部分题解解法相同，此题解给出算法时间复杂度的证明。

  思路

• 若 欠 钱，则从 向 连一条有向边。统计每一点的入度。
• 若节点 的入度为 ，则 必须得到市长的帮助，答案直接加上 的出边。
• 拿到钱的 会将钱分给他欠钱的人，于是我们暴力将钱沿着路线往下分。
• 剩下的没环完的人一定在环上。
• 遍历环，考虑给环上的一个人 补钱。设他现在有的钱为 ，他欠的钱为 ，欠他的钱为 。则
• 给 补的钱为：。
• 给其它点补的钱为：。
• 总共补的钱为：。

时间复杂度证明

• 总时间复杂度：。
• 操作 ：若节点 的入度为 ，则得到市长的帮助并暴力将钱沿着路线往下分。
• 由于每人要么被市长给钱，要么被给钱，最多跑 次，所以操作 的复杂度为 。
• 操作 ：遍历环，考虑给环上的一个人 补钱。
• 环最大长度为 ，而我们以 的时间计算贡献。因此时间复杂度为 。
• 综上，时间复杂度为 。

代码

码风粗鄙。可参考其它题解的代码。

#include<bits/stdc++.h>
using namespace std;
int n;
int g[200005],c[200005];
int rd[200005];
int now[200005];
signed main(){
    cin>>n;
    int v;
    for(int i=1;i<=n;i++){
        cin>>g[i]>>c[i];
        rd[g[i]]++;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(rd[i]==0){
            for(int u=i;rd[u]==0;u=g[u]){
                ans+=max(c[u]-now[u],0);
                rd[g[u]]--;
                now[g[u]]+=c[u];
                rd[u]=-1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(rd[i]>0){
            int maxn=2e9+10;
            int fa=i; 
            for(int u=g[i];rd[u];u=g[u]){
                ans+=max(c[u]-c[fa]-now[u],0);
                int z=max(c[u]-now[u],0)-max(c[u]-c[fa]-now[u],0);
                maxn=min(maxn,z);
                rd[u]--;
                fa=u;
            }
            ans+=maxn;
        }
    }
    cout<<ans;
    return 0;
}