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 main()
{
    int n, m, S, T, x, y, z;
    cin >> n >> m >> S >> T;
    Flow u(n, S, T);
    while (m--)
    {
        scanf("%d%d%d", &x, &y, &z);
        u.addEdge(x, y, z);
    }
    cout << u.maxFlow() << endl;
}

Code mẫu của happyboy99x

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

struct Edge {
    int from, to, cap, flow, index;
    Edge(int from, int to, int cap, int flow, int index) :
        from(from), to(to), cap(cap), flow(flow), index(index) {}
};

struct PushRelabel {
    int N;
    vector<vector<Edge> > G;
    vector<LL> excess;
    vector<int> dist, active, count;
    queue<int> Q;

    PushRelabel(int N) : N(N), G(N), excess(N), dist(N), active(N), count(2*N) {}

    void AddEdge(int from, int to, int cap) {
        G[from].push_back(Edge(from, to, cap, 0, G[to].size()));
        if (from == to) G[from].back().index++;
        G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1));
    }

    void Enqueue(int v) { 
        if (!active[v] && excess[v] > 0) { active[v] = true; Q.push(v); } 
    }

    void Push(Edge &e) {
        int amt = int(min(excess[e.from], LL(e.cap - e.flow)));
        if (dist[e.from] <= dist[e.to] || amt == 0) return;
        e.flow += amt;
        G[e.to][e.index].flow -= amt;
        excess[e.to] += amt;    
        excess[e.from] -= amt;
        Enqueue(e.to);
    }

    void Gap(int k) {
        for (int v = 0; v < N; v++) {
            if (dist[v] < k) continue;
            count[dist[v]]--;
            dist[v] = max(dist[v], N+1);
            count[dist[v]]++;
            Enqueue(v);
        }
    }

    void Relabel(int v) {
        count[dist[v]]--;
        dist[v] = 2*N;
        for (int i = 0; i < G[v].size(); i++) 
            if (G[v][i].cap - G[v][i].flow > 0)
                dist[v] = min(dist[v], dist[G[v][i].to] + 1);
        count[dist[v]]++;
        Enqueue(v);
    }

    void Discharge(int v) {
        for (int i = 0; excess[v] > 0 && i < G[v].size(); i++) Push(G[v][i]);
        if (excess[v] > 0) {
            if (count[dist[v]] == 1) 
                Gap(dist[v]); 
            else
                Relabel(v);
        }
    }

    LL GetMaxFlow(int s, int t) {
        count[0] = N-1;
        count[N] = 1;
        dist[s] = N;
        active[s] = active[t] = true;
        for (int i = 0; i < G[s].size(); i++) {
            excess[s] += G[s][i].cap;
            Push(G[s][i]);
        }

        while (!Q.empty()) {
            int v = Q.front();
            Q.pop();
            active[v] = false;
            Discharge(v);
        }

        LL totflow = 0;
        for (int i = 0; i < G[s].size(); i++) totflow += G[s][i].flow;
        return totflow;
    }
};

int main() {
    ios::sync_with_stdio(false);
    int n, m, s, t; cin >> n >> m >> s >> t; --s; --t;
    PushRelabel net (n);
    for(int i = 0; i < m; ++i) {
        int u, v, c; cin >> u >> v >> c; --u; --v;
        net.AddEdge(u, v, c);
    }
    cout << net.GetMaxFlow(s, t) << '\n';
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

struct Edge {
    int u, v;
    int capacity;
    int flow;
};

struct Network {
    int n;
    int source, sink;

    vector<vector<int> > a;
    vector<Edge> E;

    vector<int> cur;
    vector<int> dist;

    Network() {}
    Network(int n, int s, int t) {
        this->n = n;
        source = s; sink = t;
        a = vector<vector<int> > (n + 1);
        cur = dist = vector<int> (n + 1);
    }

    void addEdge(int u, int v, int c) {
        a[u].push_back(E.size()); E.push_back({u, v, c, 0});
        a[v].push_back(E.size()); E.push_back({v, u, 0, 0});
    }

    bool bfs() {
        fill(dist.begin(), dist.end(), -1);
        queue<int> Q; Q.push(source); dist[source] = 0;
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            for (int i = 0; i < a[u].size(); ++i) {
                int id = a[u][i], v = E[id].v;
                if (dist[v] < 0 && E[id].flow < E[id].capacity) {
                    dist[v] =  dist[u] + 1;
                    Q.push(v);
                }
            }
        }
        return dist[sink] >= 0;
    }

    int dfs(int u, int flow) {
        if (!flow) return 0;
        if (u == sink) return flow;
        for (; cur[u] < a[u].size(); ++cur[u]) {
            int id = a[u][cur[u]], v = E[id].v;
            if (dist[v] != dist[u] + 1) continue;
            int delta = dfs(v, min(flow, E[id].capacity - E[id].flow));
            if (delta) {
                E[id].flow += delta; E[id ^ 1].flow -= delta;
                return delta;
            }
        }
        return 0;
    }

    int maxFlow() {
        int ans = 0;
        while (bfs()) {
            fill(cur.begin(), cur.end(), 0);
            while (true) {
                int delta = dfs(source, INF);
                if (!delta) break;
                ans += delta;
            }
        }
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    Network G (n, s, t);
    while (m--) {
        int u, v, c;
        cin >> u >> v >> c;
        G.addEdge(u, v, c);
    }
    cout << G.maxFlow() << endl;
    return 0;
}

Code mẫu của RR

// Accepted
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <complex>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

#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 EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)

#define DEBUG(x) { cout << #x << " = "; cout << (x) << endl; }
#define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
#define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }

#define sqr(x) ((x) * (x))
using namespace std;

// Fastest flow

struct Edge {
    int u, v, c, f;
    int next;
};

struct MaxFlow {
    int n, s, t;
    vector< Edge > edges;
    vector<int> head, current, h, avail;
    vector<long long> excess;

    MaxFlow(int n) : n(n), head(n, -1), current(n, -1), h(n), avail(n), excess(n) {
        edges.clear();
    }

    void addEdge(int u, int v, int c) {
        Edge xuoi = {u, v, c, 0, head[u]};
        head[u] = edges.size(); edges.push_back(xuoi);
        Edge nguoc = {v, u, 0, 0, head[v]};
        head[v] = edges.size(); edges.push_back(nguoc);
    }

    long long getFlow(int _s, int _t) {
        s = _s; t = _t;
        init();

        int now = 0;
        queue<int> qu[2];
        REP(x,n)
            if (x != s && x != t && excess[x] > 0)
                qu[now].push(x);

        globalLabeling();

        int cnt = 0, ok = 0;
        while (!qu[now].empty()) {
            while (!qu[1-now].empty()) qu[1-now].pop();

            while (!qu[now].empty()) {
                int x = qu[now].front(); qu[now].pop();
                // DEBUG(x);
                while (current[x] >= 0) {
                    int p = current[x];
                    if (edges[p].c > edges[p].f && h[edges[p].u] > h[edges[p].v]) {
                        bool need = (edges[p].v != s && edges[p].v != t && !excess[edges[p].v]);
                        push(current[x]);
                        if (need) qu[1-now].push(edges[p].v);
                        if (!excess[x]) break;
                    }
                    current[x] = edges[current[x]].next;
                }

                if (excess[x] > 0) {
                    lift(x);
                    current[x] = head[x];
                    qu[1-now].push(x);
                    cnt++;
                    if (cnt == n) {
                        globalLabeling();
                        cnt=0;
                    }
                }
            }
            now = 1 - now;
        }
        return excess[t];
    }

private:
    void init() {
        REP(i,n) current[i] = head[i];

        int p = head[s];
        while (p >= 0) {
            edges[p].f = edges[p].c;
            edges[p^1].f -= edges[p].c;
            excess[edges[p].v] += edges[p].c;
            excess[s] -= edges[p].c;
            p = edges[p].next;
        }
        FOR(v,0,n-1) h[v] = 1;
        h[s] = n; h[t] = 0;
    }

    void push(int i) {
        long long delta = min(excess[edges[i].u], (long long) edges[i].c - edges[i].f);
        edges[i].f += delta; edges[i^1].f -= delta;
        excess[edges[i].u] -= delta;
        excess[edges[i].v] += delta;
    }

    void lift(int u) {
        int minH = 2 * n;
        int p = head[u];
        while (p>=0) {
            if (edges[p].c > edges[p].f)
                minH = min(minH, h[edges[p].v]);
            p = edges[p].next;
        }
        h[u] = minH + 1;
    }

    void globalLabeling() {
        REP(i,n) avail[i] = 1, h[i] = 0;
        h[s] = n; h[t] = 0;
        queue<int> q; q.push(t); avail[t] = false;

        while (!q.empty()) {
            int x = q.front(); q.pop();
            int p = head[x];
            while (p >= 0) {
                int pp = p^1;
                if (avail[edges[pp].u] && edges[pp].f < edges[pp].c) {
                    h[edges[pp].u] = h[x] + 1;
                    avail[edges[pp].u] = 0;
                    q.push(edges[pp].u);
                }
                p = edges[p].next;
            }
            if (q.empty() && avail[s]) {
                avail[s] = false;
                q.push(s);
            }
        }
        REP(x,n) current[x] = head[x];
    }
};

int main() {
    ios :: sync_with_stdio(false);
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    --s; --t;
    MaxFlow flow(n);
    while (m--) {
        int u, v, c; cin >> u >> v >> c;
        --u; --v;
        flow.addEdge(u, v, c);
    }
    cout << flow.getFlow(s, t) << endl;
}

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 1011
#define maxe 1000011

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, m, u, v, c;
    scanf("%d %d %d %d", &n, &m, &u, &v);
    dinic.init(u, v);
    rep(i, m){
        scanf("%d %d %d", &u, &v, &c); 
        dinic.add(u, v, c, 0); 
    }    
    printf("%d\n",dinic.maxflow());
}

Code mẫu của ll931110

{$MODE DELPHI}
program NKFLOW;
const
  input  = '';
  output = '';
  maxn = 1000;
type
  PNode = ^TNode;
  TNode = record
    adj: integer;
    link: PNode;
  end;
var
  c,f: array[1..maxn,1..maxn] of integer;
  trace,queue: array[1..maxn] of integer;
  n,m,s,t: integer;
  a: array[1..maxn] of PNode;

procedure add(u,v: integer);
var
  P: PNode;
begin
  New(P);
  P^.adj := v;
  P^.link := a[u];
  a[u] := P;
end;

procedure init;
var
  fi: text;
  i,u,v: integer;
begin
  assign(fi, input);
    reset(fi);

  readln(fi, n, m, s, t);
  fillchar(c, sizeof(c), 0);
  fillchar(f, sizeof(f), 0);

  for i := 1 to m do
    begin
      readln(fi, u, v, c[u,v]);
      add(u,v);
    end;

  close(fi);
end;

function FindPath: boolean;
var
  va,st,front,rear: integer;
  u: PNode;
begin
  fillchar(trace, sizeof(trace), 0);
  front := 1;
  rear := 1;
  queue[1] := s;
  trace[s] := -1;

  repeat
    st := queue[front];
    inc(front);
    u := a[st];

    while u <> nil do
      begin
        va := u^.adj;
        if (trace[va] = 0) and (c[st,va] > f[st,va]) then
          begin
            trace[va] := st;
            if va = t then exit(true);

            inc(rear);
            queue[rear] := va;
          end;

        u := u^.link;
      end;
  until front > rear;
  FindPath := false;
end;

procedure IncFlow;
var
  delta,u,v: integer;
begin
  delta := high(longint);
  v := t;

  repeat
    u := trace[v];
    if c[u,v] - f[u,v] < delta then delta := c[u,v] - f[u,v];
    v := u;
  until v = s;

  v := t;
  repeat
    u := trace[v];
    f[u,v] := f[u,v] + delta;
    f[v,u] := f[v,u] - delta;
    v := u;
  until v = s;
end;

procedure FordFulkerson;
begin
  repeat
    if not FindPath then break;
    IncFlow;
  until false;
end;

procedure printresult;
var
  fo: text;
  cost,i,j: integer;
begin
  assign(fo, output);
    rewrite(fo);

  cost := 0;
  for i := 1 to n do
    if f[s,i] > 0 then cost := cost + f[s,i];

  writeln(fo, cost);
  close(fo);
end;

begin
  init;
  FordFulkerson;
  printresult;
end.

Code mẫu của skyvn97

#include<bits/stdc++.h>
using namespace std;

struct DinicFlow {
    static const int INF = (int) 1e9 + 7;
    int numNode, numEdge;
    vector<int> dist, head, work;
    vector<int> point, flow, capa, next;

    DinicFlow(int n = 0) {
        numNode = n;
        numEdge = 0;
        dist.assign(n + 7, 0);
        head.assign(n + 7, -1);
        work.assign(n + 7, 0);
    }

    int addEdge(int u, int v, int c1, int c2 = 0) {
        int ret = numEdge;
        point.push_back(v); capa.push_back(c1); flow.push_back(0); next.push_back(head[u]); head[u] = numEdge++;
        point.push_back(u); capa.push_back(c2); flow.push_back(0); next.push_back(head[v]); head[v] = numEdge++;
        return ret;
    }

    bool bfs(int s, int t) {
        queue<int> q;
        for (int i = 1; i <= numNode; i++) dist[i] = -1;
        dist[s] = 0; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = head[u]; i >= 0; i = next[i]) if (flow[i] < capa[i] && dist[point[i]] < 0) {
                dist[point[i]] = dist[u] + 1;
                q.push(point[i]);
            }
        }
        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 (flow[i] < capa[i] && dist[point[i]] == dist[s] + 1) {
            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) {
        for (int i = 1; i <= numNode; i++) flow[i] = 0;
        int totFlow = 0;
        while (bfs(s, t)) {
            for (int i = 1; i <= numNode; i++) work[i] = head[i];
            while (true) {
                int d = dfs(s, t, INF);
                if (d == 0) break;
                totFlow += d;
            }
        }
        return totFlow;
    }

    int getFlow(int id) const {
        return flow[id];
    }
};

int main(void) {
    int n, m, src, snk; cin >> n >> m >> src >> snk;
    DinicFlow df(n);
    for (int love = 0; love < m; love++) {
        int u, v, c; cin >> u >> v >> c;
        df.addEdge(u, v, c);
    }
    cout << df.maxFlow(src, snk) << endl;
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>

using namespace std;

#define maxn 1010

int n, m, s, t, soluong;
int a[maxn][maxn], f[maxn][maxn];
int q[maxn], la[maxn], e[maxn];

void tang() {
    int dt = e[t];
    soluong += dt;
    int v = t;
    while(la[v]!=v) {
        int u = la[v];
        if(u<0) {
            f[v][-u] -= dt;
            v = -u;
        }
        else {
            f[u][v] += dt;
            v = u;  
        }
    }   
}

bool bfs() {
    int l, r;
    q[l=r=0] = s;
    memset( la, 0, sizeof(la));
    memset( e, 0, sizeof(e));
    la[s] = s;
    e[s] = 1000000000;
    while(l<=r) {
        int u = q[l++];
        for(int v=1;v<=n;++v) if(e[v]==0) {
            if(a[u][v]>f[u][v]) {
                e[v] = min( e[u], a[u][v] - f[u][v]);
                q[++r] = v;
                la[v] = u;  
            }   
            else if(f[v][u]>0) {
                e[v] = min( e[u], f[v][u]);
                q[++r] = v;
                la[v] = -u; 
            }
        }   
        if(e[t]!=0) {
            tang();
            return true;
        }   
    }
    return false;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for(int i=0;i<m;++i) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        a[u][v] = c;
    }
    while(bfs());
    cout << soluong << endl;
    //system("pause");
    return 0;
}