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>
#define ii pair<int, int>
#define iii pair<int, ii>
#define X first
#define Y second

const int N = 111;
const int oo = trunc(1e9);
const int V = N * N;
using namespace std;
vector<iii> e;
vector<int> a[N];
int c[N][N], f[N][N], T[N], Q[N];
int m, n, s, t, res, ans;

void Enter() {
    //freopen("NKNET.in", "r", stdin);
    scanf("%d %d\n", &n, &m);
    int u, v, c;
    for(int i=1; i<=m; i++) {
        scanf("%d %d %d\n", &u, &v, &c);
        e.push_back(iii(c, ii(u, v)));
        a[u].push_back(v);
        a[v].push_back(u);
    }
    scanf("%d %d", &s, &t);
}

void Init(int lim) {
    //initialize network
    int i, j, u, v;
    for(i=1; i<=n; i++) {
        a[i].clear();
        for(j=1; j<=n; j++) {
            f[i][j] = 0;
            c[i][j] = V;
        }
    }
    for(i=0; i<m; i++)
    if (e[i].X > lim) {
        u = e[i].Y.X;
        v = e[i].Y.Y;
        a[u].push_back(v);
        a[v].push_back(u);
    }
}

void Init2(int lim) {
    int i, j, u, v;
    for(i=1; i<=n; i++) {
        a[i].clear();
        for(j=1; j<=n; j++) {
            f[i][j] = 0;
            c[i][j] = V;
        }
    }
    for(i=0; i<m; i++) {
        u = e[i].Y.X;
        v = e[i].Y.Y;
        a[u].push_back(v);
        a[v].push_back(u);

        if (e[i].X <= lim)
            c[u][v] = c[v][u] = 1;
    }
}

bool FindPath() {
    int l=1, r=1, u, v, i;
    Q[1] = s;
    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 == t) return true;
            }
        }
    }
    return false;
}

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

int maxFlow() {
    while (FindPath()) IncFlow();
    int flow = 0;
    for(int i=0; i<a[s].size(); i++)
        flow += f[s][a[s][i]];
    return flow;
}

int main()
{
    Enter();
    //BinarySearch the answer
    int l = 0, r = V, mid;
    while (l <= r) {
        mid = (l + r) / 2;
        Init(mid);
        if (FindPath()) {
            l = mid + 1;
        }
        else {
            res = mid;
            r = mid - 1;
        }
    }
    Init2(res);
    ans = maxFlow();
    printf("%d\n", ans);
    for(int i=1; i<=n; i++)
    if (i == s || T[i] > 0) {
        for(int j=0; j<a[i].size(); j++) {
            int v = a[i][j];
            if (T[v] == 0) printf("%d %d\n", i, v);
        }
    }
    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
uses math;
const
  finp='';
  fout='';
  maxn=101;
  oo=1000000;
var
  s,t,m,n:longint;
  queue,trace:array[0..maxn] of longint;
  c,c2,f:array[0..maxn,0..maxn] of longint;
procedure readinp;
var
  i,u,v:longint;
begin
  assign(input,finp);  reset(input);
  read(n,m);
  for i:=1 to m do
  begin
    read(u,v,c[u,v]);
    c[v,u]:=c[u,v];
  end;
  read(s,t);
  close(input);
end;
function findpath:boolean;
var
  first,last,i,j:longint;
begin
  fillchar(trace,sizeof(trace),0);
  first:=0;
  last:=1;
  queue[1]:=s;
  trace[s]:=n+1;
  while first<last do
  begin
    inc(first);
    i:=queue[first];
    for j:=1 to n do
    if (trace[j]=0) and (f[i,j]<c[i,j]) then
      begin
        trace[j]:=i;
        inc(last);
        queue[last]:=j;
        if j=t then exit(true);
      end;
  end;
  exit(false);
end;
procedure incflow;
var
  i,j,delta:longint;
begin
  delta:=oo;
  j:=t;
  repeat
    i:=trace[j];
    if delta>c[i,j]-f[i,j] then delta:=c[i,j]-f[i,j];
    j:=i;
  until j=s;
  j:=t;
  repeat
    i:=trace[j];
    inc(f[i,j],delta);
    dec(f[j,i],delta);
    j:=i;
  until j=s;
end;
function check(val:longint):boolean;
var
  i,j,cost:longint;
  ok:boolean;
begin
  c2:=c;
  for i:=1 to n do
  for j:=1 to n do
    if (c[i,j]<>0) and (c[i,j]<=val) then c[i,j]:=1
    else if c[i,j]>val then c[i,j]:=oo;
  fillchar(f,sizeof(f),0);
  ok:=false;
  repeat
    if not findpath then break;
    incflow;
  until ok;
  cost:=0;
  for i:=1 to n do
    if f[s,i]>0 then inc(cost,f[s,i]);
  c:=c2;
  if cost>=oo then exit(false) else exit(true);
end;
procedure printresult(val:longint);
var
  i,j,cost:longint;
  ok:boolean;
  fo:text;
begin
  for i:=1 to n do
  for j:=1 to n do
    if (c[i,j]<>0) and (c[i,j]<=val) then c[i,j]:=1
    else if (c[i,j]<>0) then c[i,j]:=oo;
  fillchar(f,sizeof(f),0);
  ok:=false;
  repeat
    if not findpath then break;
    incflow;
  until ok;
  cost:=0;
  for i:=1 to n do
    if f[s,i]>0 then inc(cost,f[s,i]);
  assign(fo,fout); rewrite(fo);
  writeln(fo,cost);
  for i:=1 to n do
  for j:=1 to n do
    if (c[i,j]<>0) and (trace[i]<>0) and (trace[j]=0)
    then writeln(fo,i,' ',j);
  close(fo);
end;
procedure solve;
var
  left,right,mid:longint;
begin
  left:=0;  right:=101;
  repeat
    mid:=(left+right) div 2;
    if check(mid) then right:=mid else left:=mid;
  until left=right-1;
  if check(left) then printresult(left) else printresult(right);
end;
begin
  readinp;
  solve;
end.

Code mẫu của ll931110

program NKNET;
const
  input  = '';
  output = '';
  maxn = 100;
  maxm = 10000;
  maxv = 1000000;
var
  a,c,f: array[1..maxn,1..maxn] of longint;
  n,m: longint;

  queue,trace: array[1..maxn] of longint;
  front,rear: longint;

  s,t: longint;
  time: longint;

  cc: longint;
  lx,ly,t1,t2: array[1..maxm] of longint;
  l1,l2: longint;

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

  read(fi, n, m);
  fillchar(a, sizeof(a), 0);

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

  readln(fi, s, t);

  close(fi);
end;

function ok(x: longint): boolean;
var
  u,v: longint;
begin
  fillchar(trace, sizeof(trace), 0);
  front := 1;  rear := 1;  queue[1] := s;
  trace[s] := -1;

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

    for v := 1 to n do
      if (trace[v] = 0) and (a[u,v] > x) then
        begin
          trace[v] := u;
          if v = t then exit(false);

          inc(rear);
          queue[rear] := v;
        end;
  until front > rear;

  ok := true;
end;

procedure settime;
var
  inf,sup,med: longint;
begin
  inf := 0;
  sup := maxn;

  repeat
    med := (inf + sup) div 2;
    if ok(med) then
      begin
        time := med;
        sup := med - 1;
      end
    else inf := med + 1;
  until inf > sup;
end;

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

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

    for v := 1 to n do
      if (trace[v] = 0) and (c[u,v] > f[u,v]) then
        begin
          trace[v] := u;
          if v = t then exit(true);
          inc(rear);  queue[rear] := v;
        end;
  until front > rear;

  FindPath := false;
end;

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

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

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

procedure FordFulkerson;
var
  i,j,u,v: longint;
begin
  fillchar(c, sizeof(c), 0);
  for i := 1 to n do
    for j := 1 to n do if a[i,j] > 0 then
        begin
          if a[i,j] <= time then c[i,j] := 1 else c[i,j] := maxv;
        end;

  fillchar(f, sizeof(f), 0);
  repeat
    if not FindPath then break;
    IncFlow;
  until false;

  cc := 0;
  l1 := 0;  l2 := 0;
  for i := 1 to n do
    if trace[i] = 0 then
      begin
        inc(l2);  t2[l2] := i;
      end
    else
      begin
        inc(l1);  t1[l1] := i;
      end;

  for i := 1 to l1 do
    for j := 1 to l2 do
      begin
        u := t1[i];  v := t2[j];
        if (c[u,v] = 1) and (f[u,v] = 1) then
          begin
            inc(cc);
            lx[cc] := u;  ly[cc] := v;
          end;
      end;
end;

procedure printresult;
var
  fo: text;
  i: longint;
begin
  assign(fo, output);
    rewrite(fo);

  writeln(fo, cc);
  for i := 1 to cc do writeln(fo, lx[i], ' ', ly[i]);

  close(fo);
end;

begin
  init;
  settime;
  FordFulkerson;
  printresult;
end.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   111
#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++)
#define fi   first
#define se   second
using namespace std;
const int INF=(int)1e9+7;
typedef pair<int,int> ii;
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,int _m) {
        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);
        int m=2*_m;
        capa=vector<int>(m+7);
        flow=vector<int>(m+7,0);
        next=vector<int>(m+7);
        point=vector<int>(m+7);
    }
    void addedge(int u,int v,int c1,int c2) {
        point[m]=v;capa[m]=c1;flow[m]=0;next[m]=head[u];head[u]=m;m++;
        point[m]=u;capa[m]=c2;flow[m]=0;next[m]=head[v];head[v]=m;m++;      
    }
    bool bfs(int s,int t) {
        FORE(it,dist) *it=-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,vector<int> &v) {
        int ret=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;
                ret+=d;
            }
        }
        v.clear();
        FOR(i,1,n) if (dist[i]>=0) v.push_back(i);
        //printf("MaxFlow %d\n",ret);
        return (ret);
    }
};
vector<ii> g[MAX];
int d[MAX];
bool src[MAX];
int n,m,s,t;
void loadgraph(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    REP(i,m) {
        int u,v,c;
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%d",&c);
        g[u].push_back(ii(v,c));
        g[v].push_back(ii(u,c));
    }   
    scanf("%d",&s);
    scanf("%d",&t);
}
bool bfs(int s,int t,int x) {
    queue<int> q;
    while (!q.empty()) q.pop();
    memset(d,-1,sizeof d);
    q.push(s);
    d[s]=0;
    while (!q.empty()) {
        int u=q.front();q.pop();
        if (u==t) return (true);
        FORE(it,g[u]) if (it->se>x) {
            int v=it->fi;
            if (d[v]<0) {
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    return (false);
}
int findtime(void) {
    int l=0;
    int r=INF;
    while (true) {
        if (l==r) return (r);
        if (r-l==1) {
            if (!bfs(s,t,l)) return (l);
            else return (r);
        }
        int m=(l+r)>>1;
        if (!bfs(s,t,m)) r=m;
        else l=m+1;
    }
}
void process(void) {
    int ans=findtime(); 
    DinicFlow G=DinicFlow(n,m);
    FOR(i,1,n) FORE(it,g[i]) {
        int j=it->fi;
        int cst;
        if (it->se<=ans) cst=1; else cst=INF;
        if (i<j) G.addedge(i,j,cst,cst);
    }
    vector<int> v;  
    vector<ii> res;
    assert(G.maxflow(s,t,v)<INF);   
    FORE(it,v) src[*it]=true;
    FORE(it,v) FORE(jt,g[*it]) if (!src[jt->fi]) res.push_back(ii(*it,jt->fi));
    printf("%d\n",res.size());
    FORE(it,res) printf("%d %d\n",it->fi,it->se);
}
int main(void) {
#ifndef ONLINE_JUDGE
    freopen("tmp.txt","r",stdin);
    printf("START\n");
#endif
    loadgraph();
    process();
    return 0;
}