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 ladpro98

#include <bits/stdc++.h>

const int N = 400005;
const long long INF = (long long)1e18;

using namespace std;

struct edge {
    int u, v, w;
    int cap, flow;
    edge() { flow = 0; }
    edge(int _u, int _v, int _w, int _cap) {
        u = _u; v = _v; w = _w; cap = _cap;
        flow = 0;
    }
    int getAdj(int _u) {
        return u ^ v ^ _u;
    }
    int getCost() {
        return flow < 0 ? -w : w;
    }
    int getResidualFlow() {
        return flow < 0 ? -flow : (cap - flow);
    }
} E[N];

int nEdge;
int n, m, source, sink;
bool inQ[N];
long long d[N];
int maxFlow;
long long minCost;
bool was[N];
int T[N];
vector<int> a[N];

void addEdge(int u, int v, int w) {
    assert(!(nEdge & 1));
    E[nEdge] = edge(u, v, w, 1);
    E[nEdge | 1] = edge(v, u, w, 1);
    a[u].push_back(nEdge);
    a[v].push_back(nEdge | 1);
    nEdge += 2;
}

bool findPath() {
    queue<int> Q;
    for (int i = 1; i <= n; ++i) d[i] = INF;
    d[source] = 0;
    Q.push(source); inQ[source] = 1;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); inQ[u] = 0;
        for (vector<int>::iterator it = a[u].begin(); it != a[u].end(); ++it) {
            if (E[*it].cap > E[*it].flow) {
                int cost = E[*it].getCost();
                int v = E[*it].getAdj(u);
                if (d[v] > d[u] + cost) {
                    T[v] = *it;
                    d[v] = d[u] + cost;
                    if (!inQ[v]) {
                        inQ[v] = 1;
                        Q.push(v);
                    }
                }
            }
        }
    }
    return d[sink] < INF;
}

void incFlow() {
    for (int v = sink; v != source; v = E[T[v]].getAdj(v))
        ++E[T[v]].flow, --E[T[v] ^ 1].flow;
    ++maxFlow;
    minCost += d[sink];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int s, f;
    cin >> n >> m >> s >> f;
    int u, v, w;
    for (int i = 0; i < m; ++i) {
        cin >> u >> v >> w;
        addEdge(u, v, w);
    }
    source = n + 1; sink = f;
    addEdge(source, s, 0);
    addEdge(source, s, 0);
    ++n;
    for (int i = 1; i <= n; ++i)
        random_shuffle(a[i].begin(), a[i].end());
    while (maxFlow < 2 && findPath()) incFlow();
    if (maxFlow < 2)
        cout << -1 << endl;
    else
        cout << minCost << endl;
    return 0;
}

Code mẫu của RR

//Written by RR

{$MODE OBJFPC}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       50111;

type
  list          =       ^node;
  node          =       record
        u       :       longint;
        c       :       int64;
        next    :       list;
        rev     :       list;
  end;

var
  f1,f2         :       text;
  ke            :       array[1..MAXN] of list;
  n,s,t         :       longint;

  first,last,spt:       longint;
  queue,trace   :       array[1..MAXN] of longint;
  d             :       array[1..MAXN] of int64;
  inq           :       array[1..MAXN] of boolean;
  tr,tr2        :       array[1..MAXN] of list;

  hpos,h        :       array[1..MAXN] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;

procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure add(u:longint; c:int64; var a:list); inline;
    var
      p:list;
    begin
      new(p); p^.u:=u; p^.c:=c;
      p^.next:=a; a:=p;
    end;

procedure inp;
    var
      i,m,u,v:longint;
      c:int64;
    begin
      read(f1,n,m);
      read(f1,s,t);
      for i:=1 to m do
        begin
          read(f1,u,v,c);
          add(u,c,ke[v]);
          add(v,c,ke[u]);
          ke[u]^.rev:=ke[v];
          ke[v]^.rev:=ke[u];
        end;
    end;

procedure findPath;
    var
      u,v:longint;
      c:int64;
      p,q:list;
    begin
      fillchar(d,sizeof(d),$77); d[s]:=0;
      fillchar(inq,sizeof(inq),false);
      first:=1; last:=1; queue[1]:=s; spt:=1; inq[s]:=true;
      while spt>0 do
        begin
          u:=queue[first]; inc(first); if first=MAXN then first:=1; dec(spt);
          inq[u]:=false;
          p:=ke[u];
          while p<>nil do
            begin
              v:=p^.u; c:=p^.c; q:=p^.rev;
              if v<>0 then
              if d[v]>d[u]+c then
                begin
                  d[v]:=d[u]+c;
                  trace[v]:=u;
                  tr[v]:=q; tr2[v]:=p;
                  if inq[v]=false then
                    begin
                      inc(last); if last=MAXN then last:=1;
                      inc(spt);
                      inq[v]:=true;
                      queue[last]:=v;
                    end;
                end; //d[v]>d[u]+c
              p:=p^.next;
            end; //while p<>nil
        end; //while spt>0
    end;

procedure truyVet;
    var
      u,v:longint;
      p:list;
    begin
      v:=t;
      while v<>s do
        begin
          u:=trace[v];
          p:=tr[v];
          p^.c:=-p^.c;
          p:=tr2[v];
          p^.u:=0;
          v:=u;
        end;
    end;

procedure solve;
    var
      res:int64;
    begin
      findPath;
      res:=d[t];
      if res>high(int64) div 2 then
        begin
          writeln(f2,-1);
          exit;
        end;
      truyVet;
      findPath;
      res:=res+d[t];
      if res>high(int64) div 2 then
        begin
          writeln(f2,-1);
          exit;
        end;
      writeln(f2,res);
    end;

begin
  openF;
  inp;
  solve;
  closeF;
end.