Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include<iostream>
#include<algorithm>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define maxn 200020
using namespace std;

int n,a[maxn],b[maxn],v[maxn],c[maxn],d[maxn],e[maxn],f[maxn],p[maxn],st[maxn];
int last,kt[maxn],re,sm,h[maxn],pp[maxn],bb[maxn*2],q[maxn];

void go(int x,int sm)
{
    e[x]=1; st[++last]=x; 
    if (!d[a[x]])
    {
       if (!e[a[x]]) go(a[x],sm);
       else
       {
           kt[sm]=1; 
           int t=a[x]; 
           do
           {
              x=st[last--];
              e[x]=2;
           } while (x!=t);
       }          
    }
    if (kt[sm]) return;
    e[x]=0; d[x]=1; --last;
}

void dfs(int x)
{
    int i;
    fr(i,p[x]+1,p[x+1])
    {
       if (e[b[i]]==2) continue;                
       dfs(b[i]);                
       re+=max(v[i]-f[b[i]],0);
       f[x]+=v[i];
    }     
}

void bfs(int x)
{
    int i=1,nq=1,j; 
    sm++; h[x]=sm; q[1]=x;
    while (i<=nq)
    {
       x=q[i++]; 
       fr(j,pp[x]+1,pp[x+1])
         if (!h[bb[j]])
         {
            h[bb[j]]=sm;
            q[++nq]=bb[j];
         }
    }     
} 

void pr(int i)
{
    int j=a[i],ii=i,t=2000000000,g;
    do
    {
        g=0; e[i]=0;
        if (c[i]+f[j]<c[j])
        {
            g=c[j]-c[i]-f[j];
            re+=g;               
        }
        if (c[j]>f[j]) t=min(t,c[j]-f[j]-g);
        else t=0;
        i=j; j=a[i];
    } while (i!=ii);
    re+=t;
}

int main()
{
    int i;
    cin >> n;
    fr(i,1,n)
    {
       scanf("%d%d",&a[i],&c[i]);
       p[a[i]]++; pp[a[i]]++; pp[i]++;
    }
    fr(i,2,n+1) 
    {
       p[i]+=p[i-1]; pp[i]+=pp[i-1];
    } 
    fr(i,1,n) 
    {
       b[p[a[i]]]=i; v[p[a[i]]--]=c[i];
       bb[pp[a[i]]--]=i; bb[pp[i]--]=a[i];
    }   
    fr(i,1,n)
      if (!h[i]) bfs(i);
    fr(i,1,n)
      if (!kt[h[i]]) 
      {
          last=0; go(i,h[i]);        
      }
    fr(i,1,n) 
      if (e[i]==2) dfs(i);
    fr(i,1,n)
      if (e[i]==2 && kt[h[i]]) 
      {
        kt[h[i]]=0;
        pr(i);
      }
    cout << re << endl;
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;

int to[N], pay[N], in[N], has[N];
bool paid[N];
int n, ans;

int getTake(int u) { return max(0, pay[u] - has[u]); }
void goPay(int u) { paid[u] = 1; has[to[u]] += pay[u]; ans += getTake(u); }

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> to[i] >> pay[i];
        ++in[to[i]];
    }
    queue<int> Q;
    for (int i = 1; i <= n; ++i) if (in[i] == 0)
        Q.push(i);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        goPay(u);
        if ((--in[to[u]]) == 0) Q.push(to[u]);
    }
    for (int v = 1; v <= n; ++v) if (!paid[v]) {
        int minTake = getTake(v), u = v;
        for (int i = to[v]; i != v; i = to[i]) if (minTake > getTake(i))
            minTake = getTake(i), u = i;
        while (!paid[u]) goPay(u), u = to[u];
    }
    cout << ans << endl;
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

//Buffer reading
int INP,AM;
#define BUFSIZE (1<<18)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        fread(BUF,1,BUFSIZE,stdin); \
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const double PI = acos(-1.0);
const int MN = 200111;

int n, to[MN], need[MN], req[MN], vao[MN], st[MN], top, done[MN];
int f[MN];

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    GN(n);
    FOR(i,1,n) {
        GN(to[i]);
        GN(need[i]); req[i] = need[i];
        vao[to[i]]++;
    }
    FOR(i,1,n) if (!vao[i]) st[++top] = i;

    ll res = 0;
    while (top) {
        int u = st[top--];
        done[u] = 1;
        int v = to[u];
        res += need[u];
        need[v] -= req[u]; if (need[v] < 0) need[v] = 0;
        vao[v]--;
        if (!vao[v]) st[++top] = v;
    }

    FOR(i,1,n)
    if (!done[i]) {
        int u = i, v;
        int sum = 0;

        done[u] = 1;
        do {
            v = to[u];
            done[v] = 1;
            f[v] = max(need[v] - req[u], 0);
            sum += f[v];
            u = v;
        } while (u != i);

        u = i;
        int best = 2000111000;
        do {
            v = to[u];
            best = min(best, need[v] - f[v] + sum);
            u = v;
        } while (u != i);
        res += best;
    }
    cout << res;
    return 0;
}

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<sstream>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 1000000001
#define mod 790972
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, x) memset(a, x, sizeof(a))
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(), a.end()
#define maxn (200000) + 10
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long ll;
int dx[] = {+1, 0, -1, 0};
int dy[] = {0, -1, 0, +1};

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}

int n, dad[maxn], debt[maxn], num[maxn] = {0}, fl[maxn] = {0}, que[maxn], have[maxn] = {0};

int main(){
  //  OPEN();
    gi(n);
    FOR(i, 1, n){
        gi(dad[i]); gi(debt[i]);
        num[dad[i]]++;
    }

    int size = 0;
    FOR(i, 1, n) if(!num[i]) que[size++] = i;

    int res = 0;
    rep(i, size){
        int u = que[i];
        fl[u] = 1;
        if(have[u] < debt[u]) res += debt[u] - have[u];
        have[dad[u]] += debt[u];
        num[dad[u]]--;
        if(!num[dad[u]]) que[size++] = dad[u];
    }

    FOR(i, 1, n) if(!fl[i]){
        fl[i] = 1;
        int MAX = oo, u = dad[i], sum = 0;
        sum += max(0, debt[u] - debt[i] - have[u]); 
        MAX = min(MAX, max(0, debt[u] - have[u]) - max(0, debt[u] - debt[i] - have[u]));
        do{
            fl[u] = 1;
            sum += max(0, debt[dad[u]] - debt[u] - have[dad[u]]);
            MAX = min(MAX, max(0, debt[dad[u]] - have[dad[u]]) - max(0, debt[dad[u]] - debt[u] - have[dad[u]]));
            u = dad[u];
        }while(u != i);

        res += MAX + sum;
    }

    printf("%d", res);

}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define maxn 200005
using namespace std;

int next[maxn];
vector<int> rev[maxn];
int owe[maxn],gain[maxn],cycleAdd[maxn];
bool oncycle[maxn],exist[maxn];
stack<int> s;
int low[maxn],num[maxn],total = 0;
long long ret = 0;
int n;

void DFS(int u) {
  low[u] = num[u] = ++total;
  s.push(u);

  int v = next[u];
  if (exist[v]) {
    if (!num[v]) {
      DFS(v);
      low[u] = min(low[u],low[v]);
    }
    else low[u] = min(low[u],num[v]);
  }

  if (low[u] != num[u]) return;
  vector<int> store;
  while (1) {
    int x = s.top();
    s.pop();
    store.push_back(x);
    exist[x] = false;
    if (x == u) break;
  }
  if (store.size() < 2) return;
  for (int i = 0; i < store.size(); i++) oncycle[store[i]] = true;
}

void markNonCycle() {
  queue<int> q;
  for (int i = 1; i <= n; i++) if (!oncycle[i] && oncycle[next[i]]) q.push(i);
  vector<int> order;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    order.push_back(u);
    for (int i = 0; i < rev[u].size(); i++) q.push(rev[u][i]);
  }
  for (int i = order.size() - 1; i >= 0; i--) {
    int u = order[i];
    ret += max(0,owe[u] - gain[u]);
    gain[next[u]] += owe[u];
  }
}

void markCycle(int start) {
  int u = start;
  while (1) {
    exist[u] = false;
    cycleAdd[next[u]] = owe[u];
    u = next[u];
    if (!exist[u]) break;
  }
  long long delta = 0,thisAdd;
  while (1) {
    delta += max(0,owe[u] - gain[u] - cycleAdd[u]);
    u = next[u];
    if (u == start) break;
  }
  thisAdd = 1LL << 60;
  while (1) {
    thisAdd = min(thisAdd,delta - max(0,owe[u] - gain[u] - cycleAdd[u]) + max(0,owe[u] - gain[u]));
    u = next[u];
    if (u == start) break;
  }
  ret += thisAdd;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d %d", &next[i], &owe[i]);
    rev[next[i]].push_back(i);
  }
  memset(exist,true,sizeof(exist));
  for (int i = 1; i <= n; i++) if (exist[i]) DFS(i);
  markNonCycle();
  memset(exist,true,sizeof(exist));
  for (int i = 1; i <= n; i++) if (exist[i] && oncycle[i]) markCycle(i);
  printf("%lld\n", ret);
}