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 <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int oo = 1 << 29;

struct edge
{
    int x, y, cap, flow;
};

struct Flow
{
    int n, S, T;
    vector < vector <int> > a;
    vector <int> cur, d;
    vector <edge> e;

    Flow() {}
    Flow(int _n, int _S, int _T)
    {
        n = _n; S = _S; T = _T;
        a = vector < vector <int> >(n + 1);
        cur = vector <int>(n + 1);
        d = vector <int>(n + 1);
    }

    void addEdge(int x, int y, int _cap)
    {
        edge e1 = {x, y, _cap, 0};
        edge e2 = {y, x, 0, 0};
        a[x].push_back(e.size()); e.push_back(e1);
        a[y].push_back(e.size()); e.push_back(e2);
    }

    int bfs()
    {
        queue <int> q;
        for (int i = 1; i <= n; i++) d[i] = -1;
        q.push(S); d[S] = 0;
        while (!q.empty() && d[T] < 0)
        {
            int x = q.front(); q.pop();
            for (int i = 0; i < int(a[x].size()); i++)
            {
                int id = a[x][i], y = e[id].y;
                if (d[y] < 0 && e[id].flow < e[id].cap)
                    q.push(y), d[y] = d[x] + 1;
            }
        }
        return d[T] >= 0;
    }

    int dfs(int x, int val)
    {
        if (!val) return 0;
        if (x == T) return val;
        for (; cur[x] < int(a[x].size()); cur[x]++)
        {
            int id = a[x][cur[x]], y = e[id].y;
            if (d[y] != d[x] + 1) continue;
            int pushed = dfs(y, min(val, e[id].cap - e[id].flow));
            if (pushed)
            {
                e[id].flow += pushed;
                e[id ^ 1].flow -= pushed;
                return pushed;
            }
        }
        return 0;
    }

    int maxFlow()
    {
        int res = 0;
        while (bfs())
        {
            for (int i = 1; i <= n; i++) cur[i] = 0;
            while (1)
            {
                int val = dfs(S, oo);
                if (!val) break;
                res += val;
            }
        }
        return res;
    }   

    int minCut()
    {
        maxFlow();
        int res = 0;
        for (int x = 1; x <= n; x++)
            if (d[x] >= 0)
                for (int i = 0; i < int(a[x].size()); i++)
                {
                    int id = a[x][i], y = e[id].y;
                    if (d[y] < 0) res += e[id].cap;
                }
        return res;
    }
};

int main()
{
    int n, x, y, z;
    cin >> n;
    Flow u(n, n, 1);
    while (scanf("%d%d%d", &x, &y, &z) == 3)
        u.addEdge(x, y, z);
    cout << u.minCut() << endl;

}

Code mẫu của happyboy99x

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

#define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i)
const int N = 5005;
struct edge {
    int u, c, f;
    edge(){}
    edge(int u, int c): u(u), c(c), f(0) {}
};
vector<vector<edge> > g;
int n, s, t, trace[N];

void addEdge(int u, int v, int d) {
    TR(g[u], i) if(i->u == v) { i->c += d; return; }
    g[u].push_back(edge(v, d));
}
void addFlow(int u, int v, int d) { TR(g[u], i) if(i->u == v) { i->f += d; return; } }

void enter() {
    scanf("%d", &n); g.resize(n); s = n-1; t = 0;
    for(int u, v, d; scanf("%d%d%d",&u,&v,&d) == 3; ) {
        --u; --v;
        addEdge(u, v, d);
        addEdge(v, u, 0);
    }
}

int FindPath() {
    memset(trace, 0, sizeof trace); trace[s] = -1;
    queue<pair<int, int> > q; q.push(pair<int, int>(s, 1000000000));
    while(!q.empty()) {
        int u = q.front().first, f = q.front().second; q.pop();
        TR(g[u], i) if(trace[i->u] == 0 && i->c > i->f) {
            trace[i->u] = u;
            q.push(pair<int, int>(i->u, min(f, i->c - i->f)));
            if(i->u == t) return min(f, i->c - i->f);
        }
    }
    return -1;
}

void MaxFlow() {
    int res = 0;
    for(int inc; (inc = FindPath()) != -1; ) {
        res += inc; int v = t;
        do {
            int u = trace[v];
            addFlow(u, v, inc);
            addFlow(v, u, -inc);
            v = u;
        } while(v != s);
    }
    printf("%d\n", res);
}

int main() {
    enter();
    MaxFlow();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 5001;
const int oo = 1000000009;
using namespace std;
int f[N][N], c[N][N], n, Q[N], T[N];
vector<int> a[N];

bool BFS() {
    int l = 1, r = 1, i, u, v;
    Q[1] = n;
    for(i=1; i<=n; i++) T[i] = 0;
    while (l<=r) {
        u = Q[l++];
        for(i=0; i<a[u].size(); i++) {
            v = a[u][i];
            if (T[v] == 0 && c[u][v]>f[u][v]) {
                Q[++r] = v;
                T[v] = u;
                if (v == 1) return true;
            }
        }
    }
    return false;
}

void IncFlow() {
    int v = 1, delta = oo, u;
    while (v != n) {
        u = T[v];
        delta = min(delta, c[u][v] - f[u][v]);
        v = u;
    }
    v = 1;
    while (v != n) {
        u = T[v];
        f[u][v] += delta;
        f[v][u] -= delta;
        v = u;
    }
}

int main()
{
    //freopen("BAOVE.in", "r", stdin);
    scanf("%d\n", &n); int u, v, w;
    while (scanf("%d %d %d\n", &u, &v, &w) == 3) {
        a[u].push_back(v); a[v].push_back(u);
        c[u][v] += w;
    }
    while (BFS()) IncFlow();
    int s = 0;
    for(int i = 0; i<a[n].size(); i++)
        s += f[n][a[n][i]];
    printf("%d", s);
    return 0;
}

Code mẫu của RR

//Wishing myself a happy lunar new year with a lot of accept solutions
//Written by Nguyen Thanh Trung
{$R+,Q+}
PROGRAM BAOVE;
CONST
  fi='';
  fo='';
  maxn=5000;
  max=10000;
  oo=1000000000;
TYPE
  rec=record v:integer; c:longint; end;
  rec2=record u,v:integer; c:longint; end;
VAR
  n:integer;
  queue,cv,trace,degt,degn,th1,th2:array[1..maxn] of integer;
  first,last:integer;
  xet:array[1..maxn] of byte;
  dt:array[1..maxn] of longint;
  et,en:array[1..max] of rec;
  ft:array[1..max] of longint;
  s1,s2:array[1..maxn+1] of integer;
  dscanh:array[1..max] of rec2;
  m:integer;
  f1,f2:text;
  fl:longint;
Procedure OpenFiles;
Begin
  Assign(f1,fi); Reset(f1);
  Assign(f2,fo); Rewrite(f2);
End;
Procedure CloseFiles;
Begin
  Close(f1); Close(f2);
End;
Procedure ReadInput;
Begin
  Readln(f1,n); m:=0;
  While not Eof(f1) do
    begin
      inc(m);
      with dscanh[m] do
        Readln(f1,u,v,c);
    end;
End;
Procedure Trans;
Var
  i:integer;
Begin
  For i:=1 to m do
  with dscanh[i] do
    begin
      inc(degt[u]);
      inc(degn[v]);
    end;
  s1[1]:=1;
  For i:=1 to n do
    s1[i+1]:=s1[i]+degt[i];
  s2[1]:=1;
  For i:=1 to n do
    s2[i+1]:=s2[i]+degn[i];
  For i:=1 to m do
  with dscanh[i] do
    begin
      et[s1[u]+th1[u]].v:=v;
      et[s1[u]+th1[u]].c:=c;
      inc(th1[u]);
      en[s2[v]+th2[v]].v:=u;
      en[s2[v]+th2[v]].c:=s1[u]+th1[u]-1;
      inc(th2[v]);
    end;
End;
Procedure Init;
Begin
  Fillchar(dt,sizeof(dt),0);
  dt[n]:=oo;
  Fillchar(xet,sizeof(xet),0);
  xet[n]:=1;
  first:=1; last:=1;
  queue[first]:=n;
  trace[n]:=0;
End;
Function min(a,b:longint):longint;
Begin
  if a<=b then min:=a else min:=b;
End;
Procedure FindPath;
Var
  u,v,i:integer;
Begin
  while first<=last do
    begin
      u:=queue[first]; inc(first);
      for i:=s1[u] to s1[u+1]-1 do
      with et[i] do
        if (xet[v]=0) and (c-ft[i]>0) then
          begin
            xet[v]:=1;
            inc(last); queue[last]:=v;
            trace[v]:=u; cv[v]:=i;
            dt[v]:=min(dt[u],c-ft[i]);
          end;
      for i:=s2[u] to s2[u+1]-1 do
      with en[i] do
        if (xet[v]=0) and (ft[c]>0) then
          begin
            xet[v]:=1;
            inc(last); queue[last]:=v;
            trace[v]:=-u; cv[v]:=c;
            dt[v]:=min(dt[u],ft[c]);
          end;
      if dt[1]>0 then exit;
    end;
End;
Procedure IncFlow;
Var
  x,pre:integer;
Begin
  x:=1;
  repeat
    pre:=trace[x];
    if pre>0 then ft[cv[x]]:=ft[cv[x]]+dt[1]
    else ft[cv[x]]:=ft[cv[x]]-dt[1];
    x:=abs(pre);
  until x=n;
End;
Procedure Solve;
Begin
  fl:=0;
  repeat
    Init;
    FindPath;
    if dt[1]>0 then IncFlow;
    fl:=fl+dt[1];
  until dt[1]=0;
End;
Procedure WriteOutput;
Begin
  Writeln(f2,fl);
End;
BEGIN
  OpenFiles;
  ReadInput;
  Trans;
  Solve;
  WriteOutput;
  CloseFiles;
END.

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<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 1111111111
#define mod 1000000007
#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 g 9.81
double const PI=4*atan(1.0);

using namespace std;

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;


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

// Dinic

#define maxn 5011
#define maxe 200011

struct Dinic{
    int s, t, E, adj[maxe], cap[maxe], flow[maxe], next[maxe], last[maxn],
    que[maxn], level[maxn], run[maxn];

    void init(int _s, int _t){
        s = _s; t = _t;
        E = 0; 
        memset(last, -1, sizeof(last));
    } 

    void add(int u, int v, int c1, int c2){
        adj[E] = v; cap[E] = c1; flow[E] = 0; next[E] = last[u]; last[u] = E++;
        adj[E] = u; cap[E] = c2; flow[E] = 0; next[E] = last[v]; last[v] = E++;
    }

    bool bfs(){
        memset(level, -1, sizeof(level));
        level[s] = 0;
        int size = 0; que[size++] = s;
        rep(i, size){
            for(int u = que[i], e = last[u]; e != -1; e = next[e]){
                int v = adj[e];
                if(level[v] == -1 && flow[e] < cap[e]){
                    level[v] = level[u] + 1;
                    que[size++] = v;
                }
            }
        }
        return level[t] != -1;
    }

    int dfs(int u, int bot){
        if(u == t) return bot;
        for(int &e = run[u]; e != -1; e = next[e]){
            int v = adj[e], delta;
            if(level[v] == level[u] + 1 && flow[e] < cap[e] && (delta = dfs(v, min(bot, cap[e] - flow[e]))) > 0){
                flow[e] += delta;
                flow[e ^ 1] -= delta;
                return delta;
            } 
        }
        return 0;
    }

    ll maxflow(){
        ll total = 0;
        while(bfs()){
            memcpy(run, last, sizeof(last));
            for(int delta = dfs(s, oo); delta > 0; delta = dfs(s, oo)) total += delta;
        }
        return total;
    }
} dinic;

int main(){
    //OPEN();
    int n, u, v, cost;
    scanf("%d", &n);
    dinic.init(n, 1);
    while(scanf("%d %d %d", &u, &v, &cost) > 0){
        dinic.add(u,v,cost,0);
    }   
    printf("%lld\n",dinic.maxflow());
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
const int INF=(int)1e9+7;
class DinicFlow {
    private:
    vector<int> dist,head,q,work;
    vector<int> capa,flow,next,point;
    int n,m;
    public:
    DinicFlow() {
        n=0;m=0;
    }
    DinicFlow(int n) {
        this->n=n;
        this->m=0;
        dist=vector<int>(n+7);
        head=vector<int>(n+7,-1);
        q=vector<int>(n+7);
        work=vector<int>(n+7);
    }
    void addedge(int u,int v,int c1,int c2) {
        point.push_back(v);capa.push_back(c1);flow.push_back(0);next.push_back(head[u]);head[u]=m;m++;
        point.push_back(u);capa.push_back(c2);flow.push_back(0);next.push_back(head[v]);head[v]=m;m++;
    }
    bool bfs(int s,int t) {
        FOR(i,1,n) dist[i]=-1;
        int sz=1;
        q[0]=s;dist[s]=0;
        REP(x,sz) {
            int u=q[x];
            for (int i=head[u];i>=0;i=next[i])
                if (dist[point[i]]<0 && flow[i]<capa[i]) {
                    dist[point[i]]=dist[u]+1;
                    q[sz]=point[i];
                    sz++;
                }
        }
        return (dist[t]>=0);
    }
    int dfs(int s,int t,int f) {
        if (s==t) return (f);
        for (int &i=work[s];i>=0;i=next[i])
            if (dist[point[i]]==dist[s]+1 && flow[i]<capa[i]) {
                int d=dfs(point[i],t,min(f,capa[i]-flow[i]));
                if (d>0) {
                    flow[i]+=d;
                    flow[i^1]-=d;
                    return (d);
                }
            }
        return (0);
    }
    int maxflow(int s,int t) {
        int totflow=0;
        while (bfs(s,t)) {
            FOR(i,1,n) work[i]=head[i];
            while (true) {
                int d=dfs(s,t,INF);
                if (d<=0) break;
                totflow+=d;
            }
        }
        return (totflow);
    }
};
int n;
DinicFlow G;
void process(void) {
    scanf("%d",&n);
    G=DinicFlow(n);
    int u,v,d;
    while (scanf("%d%d%d",&u,&v,&d)==3) G.addedge(u,v,d,0);
    cerr << 123 << endl;
    printf("%d",G.maxflow(n,1));
}
int main(void) {
#ifndef ONLINE_JUDGE
    freopen("tmp.txt","r",stdin);
#endif
    process();
    return 0;
}