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 happyboy99x

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

#define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int N = 255, INF = 1e9;
vector<pair<int, int> > g[4*N+2];
vector<int> c, f;
pair<int, int> res[N];
int n, m;

void addEdge(int u, int v, int lim) {
    g[u].push_back(make_pair(v, c.size()));
    g[v].push_back(make_pair(u, c.size()+1));
    c.push_back(lim); c.push_back(0);
    f.push_back(0); f.push_back(0);
}

void enter() {
    cin >> n >> m;
    for(int i = 0; i < m; ++i) addEdge(i, m+i, 1);
    string s; getline(cin, s);
    for(int i = 0; i < n; ++i) {
        getline(cin, s);
        stringstream inp (s);
        for(int x; inp >> x; --x, addEdge(2*m+i, x, 1));
        addEdge(2*(m+n), 2*m+i, 1);
    }
    for(int i = 0; i < n; ++i) {
        getline(cin, s);
        stringstream inp (s);
        for(int x; inp >> x; --x, addEdge(m+x, 2*m+n+i, 1));
        addEdge(2*m+n+i, 2*(m+n)+1, 1);
    }
}

void maxflow(int s, int t, int n) {
    while(true) {
        vector<pair<int, int> > tr (n, make_pair(INF, INF));
        tr[s] = make_pair(-1, -1);
        queue<int> q; q.push(s);
        while(!q.empty()) {
            int u = q.front(); q.pop();
            if(u == t) break;
            TR(g[u], it) {
                int v = it->first, e = it->second;
                if(c[e] - f[e] > 0 && tr[v].first == INF)
                    tr[v] = make_pair(u, e), q.push(v);
            }
        }
        if(tr[t].first == INF) break;
        int delta = INF;
        for(int u = tr[t].first, v = t; u != -1; v = u, u = tr[u].first)
            delta = min(delta, c[tr[v].second] - f[tr[v].second]);
        for(int u = tr[t].first, v = t; u != -1; v = u, u = tr[u].first) {
            f[tr[v].second] += delta;
            f[tr[v].second ^ 1] -= delta;
        }
    }
}

void trace() {
    fill(res, res+m, make_pair(-1, -1));
    for(int i = 0; i < m; ++i) TR(g[i], it) {
        int v = it->first, e = it->second;
        if(f[e] == -1) TR(g[m+i], it) {
            int v2 = it->first, e2 = it->second;
            if(f[e2] == 1) res[i] = make_pair((v-2*m)%n, (v2-2*m)%n);
        }
    }
    for(int i = 0; i < m; ++i)
        cout << res[i].first + 1 << ' ' << res[i].second + 1 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    maxflow(2*(m+n), 2*(m+n)+1, 2*(m+n+1));
    trace();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

const int N = 1111;
const int INF = int(1e9);

using namespace std;

int n, nProblem;

int contestant(int side, int id) {
  return n * side + id;
}

int problem(bool out, int id) {
  return n + n + nProblem * out + id;
}

struct edge {
  int u, v;
  int cap, flow;

  edge(int _u, int _v, int _c) {
    u = _u; v = _v; cap = _c;
    flow = 0;
  }
};

struct network {
  int n;
  int source, sink;
  int maxFlow;
  int T[N];
  vector<int> a[N];
  vector<edge> E;

  void addEdge(int u, int v, int c) {
    a[u].push_back(E.size()); //* forward
    a[v].push_back(E.size() + 1); //* reverse
    E.push_back(edge(u, v, c));
    E.push_back(edge(v, u, 0)); //* directed graph
  }

  bool findPath() {
    queue<int> Q;
    Q.push(source);
    for (int i = 1; i <= n; ++i)
      T[i] = 0;
    while (!Q.empty()) {
      int u = Q.front(); Q.pop();
      for (int id: a[u]) {
        int v = E[id].v;
        if (T[v] == 0 && E[id].cap > E[id].flow) {
          T[v] = id;
          if (v == sink) return 1;
          Q.push(v);
        }
      }
    }
    return 0;
  }

  void incFlow() {
    int delta = INF;
    for (int v = sink, u = T[v]; v != source; v = E[u].u, u = T[v])
      delta = min(delta, E[u].cap - E[u].flow);
    for (int v = sink, u = T[v]; v != source; v = E[u].u, u = T[v])
      E[u].flow += delta, E[u ^ 1].flow -= delta;
    maxFlow += delta;
  }

  void edmondsKarp() {
    while (findPath()) incFlow();
  }

  int getFlow(int u, int v) {
    for (int id: a[u])
    if (E[id].v == v)
     return E[id].flow;
    return 0;
  }
} G;

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
#ifdef _LAD_
  freopen("FLOW1.txt", "r", stdin);
#endif // _LAD_
  cin >> n >> nProblem;

  G.source = n + n + nProblem + nProblem + 1;
  G.sink = G.n = G.source + 1; //* number of vertexes equals sink

  string line;
  getline(cin, line);
  for (int side = 0; side <= 1; ++side) {
    for (int i = 1; i <= n; ++i) {
      getline(cin, line);
      istringstream input(line);
      int prob;
      while (input >> prob) {
        if (side == 0)
          G.addEdge(contestant(side, i), problem(0, prob), 1);
        else
          G.addEdge(problem(1, prob), contestant(side, i), 1);
      }
    }
  }

  for (int i = 1; i <= n; ++i)
    G.addEdge(G.source, contestant(0, i), 1);
  for (int i = 1; i <= n; ++i)
    G.addEdge(contestant(1, i), G.sink, 1);
  for (int i = 1; i <= nProblem; ++i)
    G.addEdge(problem(0, i), problem(1, i), 1);

  G.edmondsKarp();
  for (int i = 1; i <= nProblem; ++i) {
    if (G.getFlow(problem(0, i), problem(1, i))) {
      for (int id: G.a[problem(0, i)])
      if (G.E[id].v <= n && G.E[id].flow) {
        cout << G.E[id].v << ' ';
        break;
      }
      for (int id: G.a[problem(1, i)])
      if (n < G.E[id].v && G.E[id].v <= n + n && G.E[id].flow) {
        cout << G.E[id].v - n << endl;
        break;
      }
    } else {
      cout << 0 << ' ' << 0 << endl;
    }
  }
  return 0;
}

Code mẫu của RR

{$R+,Q+}
PROGRAM FLOW1;
CONST
  fi='';
  fo='';
  maxn=255;
  max=2;
TYPE
  stack=^ds;
  ds=record data:integer; next:stack; end;
VAR
  n,m:byte;
  c,d:array[0..maxn*4+1,0..maxn*4+1] of byte;
  xet:array[0..maxn*4+1] of boolean;
  dt:array[0..maxn*4+1] of shortint;
  pre:array[0..maxn*4+1] of integer;
  top:stack;
  timeold:longint;
Procedure ReadInput;
Var
  f:text;
  i,j:integer;
Begin
  Assign(f,fi); Reset(f);
  Readln(f,n,m);
  For i:=1 to n do
  begin
    While not Eoln(f) do
      begin
        Read(f,j);
        c[i,n+j]:=1;
      end;
    Readln(f);
  end;
  For i:=1 to n do
  begin
    While not Eoln(f) do
      begin
        Read(f,j);
        c[n+m+j,n+2*m+i]:=1;
      end;
    Readln(f);
  end;
  Close(f);
End;
Procedure Init;
Var
  i:integer;
Begin
  For i:=1 to n do c[0,i]:=1;
  For i:=1 to n do c[2*m+n+i,2*m+2*n+1]:=1;
  For i:=1 to m do c[n+i,n+m+i]:=1;
End;
Procedure WriteOutput;
Var
  f:text;
  i,j:integer;
  found:boolean;
Begin
  Assign(f,fo); Rewrite(f);
  For i:=1 to m do
    begin
      found:=false;
      For j:=1 to n do
        If d[j,n+i]=1 then
          begin Write(f,j,' '); found:=true; end;
      If not found then Writeln(f,'0 0');
      For j:=1 to n do
        If d[n+m+i,2*m+n+j]=1 then
          begin Write(f,j,' '); end;
      If found then Writeln(f);
    end;
  Close(f);
End;
Procedure Push(a:integer);
Var
  p:stack;
Begin
  New(p); p^.data:=a; p^.next:=top; top:=p;
End;
Procedure Pop(var a:integer);
Var
  p:stack;
Begin
  p:=top; a:=p^.data; top:=p^.next; Dispose(p);
End;
Procedure KhoiTri;
Var
  i:integer;
Begin
  For i:=1 to 2*m+2*n+1 do xet[i]:=false;
  For i:=1 to 2*m+2*n+1 do dt[i]:=max;
  For i:=1 to 2*m+2*n+1 do pre[i]:=0;
  xet[0]:=true;
  dt[0]:=max;
  top:=nil;
  Push(0);
End;
Function min(a,b:shortint):shortint;
Begin
  If a<b then min:=a else min:=b;
End;
Procedure GanNhan(u:integer);
Var
  i:integer;
Begin
  For i:=1 to 2*m+2*n+1 do
    If (not xet[i]) and (d[u,i]<c[u,i]) and (c[u,i]>0) then
      begin
        xet[i]:=true;
        Push(i);
        dt[i]:=min(dt[u],c[u,i]-d[u,i]);
        pre[i]:=u;
      end
  else
    If (not xet[i]) and (d[i,u]>0) and (c[i,u]>0) then
      begin
        xet[i]:=true;
        Push(i);
        dt[i]:=min(d[i,u],dt[u]);
        pre[i]:=-u;
      end;
End;
Procedure TangLuong;
Var
  x,truoc:integer;
Begin
  x:=2*m+2*n+1;
  repeat
    truoc:=pre[x];
    If truoc>=0 then d[truoc,x]:=d[truoc,x]+dt[2*m+2*n+1]
    else d[x,-truoc]:=d[x,-truoc]-dt[2*m+2*n+1];
    truoc:=abs(truoc);
    x:=truoc;
  until x=0;
End;
Procedure Solve;
Var
  u:integer;
Begin
  repeat
    KhoiTri;
    While (top<>nil) and (not xet[2*m+2*n+1]) do
      begin
        Pop(u);
        GanNhan(u);
      end;
    TangLuong;
  until not xet[2*m+2*n+1];
End;
BEGIN
  ReadInput;
  Init;
  Solve;
  WriteOutput;
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<sstream>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 111111111
#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 MS(a, x) memset(a, x, sizeof(a))
#define SZ(a) (int)(a.size())
//#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;

// Dinic

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

#define maxn 1311
#define maxe (1 << 20)

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 n, m, x;
char s[11111];
vector<pair<int, int> > V1[300], V2[300];

int main(){
    //OPEN();
    scanf("%d %d\n", &n, &m);
    dinic.init(0, 2 * n + 2 * m + 1);
    FOR(i, 1, m) dinic.add(n + i, n + m + i, 1, 0);
    FOR(i, 1, n) dinic.add(0, i, 1, 0);
    FOR(i, 1, n) dinic.add(n + m + m + i, n + n + m + m + 1, 1, 0);
    FOR(i, 1, n){
        gets(s);
        istringstream iss(s);
        while(iss >> x){
            V1[x].PB(MP(dinic.E, i));
            dinic.add(i, n + x, 1, 0);
        }
    }

    FOR(i, 1, n){
        gets(s);
        istringstream iss(s);
        while(iss >> x){
            V2[x].PB(MP(dinic.E, i));
            dinic.add(n + m + x, n + m + m + i, 1, 0);
        }
    }

   // printf("%lld\n",dinic.maxflow());
    dinic.maxflow();

    FOR(i, 1, m){
        int t1 = 0, t2 = 0;
        rep(j, SZ(V1[i])) if(dinic.flow[V1[i][j].fi]) t1 = V1[i][j].se;
        rep(j, SZ(V2[i])) if(dinic.flow[V2[i][j].fi]) t2 = V2[i][j].se;
        printf("%d %d\n",t1,t2);
    }
}

Code mẫu của ll931110

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

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

  New(P);
  P^.val := u;
  P^.link := a[v];
  a[v] := P;
end;

procedure init;
var
  fi: text;
  i,v: integer;
begin
  fillchar(c, sizeof(c), 0);
  fillchar(f, sizeof(f), 0);

  assign(fi,input);
    reset(fi);

  readln(fi, n, m);
  s := 0;
  t := 2 * (m + n) + 1;
  for i := 1 to n do
    begin
      add(s,i,1);
      add(n + 2 * m + i,t,1);
    end;

  for i := 1 to n do
    begin
      while not Eoln(fi) do
        begin
          read(fi, v);
          add(i, n + v,1);
        end;
      readln(fi);
    end;

  for i := 1 to m do add(n + i,n + m + i,1);
  for i := 1 to n do
    begin
      while not Eoln(fi) do
        begin
          read(fi, v);
          add(n + m + v,n + 2 * m + i,1);
        end;
      readln(fi);
    end;

  close(fi);
end;

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

  front := 1;
  rear := 1;
  queue[1] := s;

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

    P := a[u];
    while P <> nil do
      begin
        v := P^.val;
        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;
        P := P^.link;
      end;
  until front > rear;

  FindPath := false;
end;

procedure IncFlow;
var
  u,v,delta: integer;
begin
  v := t;
  delta := high(integer);
  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;
  i,j,u,v: integer;
begin
  assign(fo, output);
    rewrite(fo);

  for i := 1 to m do
    begin
      u := 0;
      for j := 1 to n do
        if f[j,n + i] = 1 then
          begin
            u := j;
            break;
          end;

      v := 0;
      for j := 1 to n do
        if f[n + m + i,n + 2 * m + j] = 1 then
          begin
            v := j;
            break;
          end;

      writeln(fo, u, ' ', v);
    end;

  close(fo);
end;

begin
  init;
  FordFulkerson;
  printresult;
end.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   257
#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 {
    public:
    vector<int> dist,head,q,work;
    vector<int> capa,flow,next,point;
    int n,m;
    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);     
    }
    int addedge(int u,int v,int c1,int c2) {        
        assert(c1==1 && c2==0);
        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++;
        return (m-2);
    }
    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) {
        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;
            }
        }
        return (ret);
    }
};
DinicFlow g;
int m,n;
vector<ii> fth[MAX],fsp[MAX];
ii res[MAX];
void init(void) {   
    cin >> n >> m;  
    int ne=2*n+m;
    string zz;
    getline(cin,zz);
    FOR(i,1,n) {
        string tmp;
        getline(cin,tmp);
        stringstream ss;
        ss << tmp;
        int t;
        while (ss >> t) {
            fth[i].push_back(ii(t,0));
            ne++;
        }
    }
    FOR(i,1,n) {
        string tmp;
        getline(cin,tmp);
        stringstream ss;
        ss << tmp;
        int t;
        while (ss >> t) {
            fsp[i].push_back(ii(t,0));
            ne++;
        }
    }   
    g=DinicFlow(2*(n+m+1),ne);      
    FOR(i,1,n) {
        FORE(it,fth[i]) it->se=g.addedge(i,n+it->fi,1,0);
        FORE(it,fsp[i]) it->se=g.addedge(n+m+it->fi,i+n+2*m,1,0);   
        g.addedge(2*(n+m)+1,i,1,0);
        g.addedge(n+2*m+i,2*(n+m+1),1,0);
    }
    FOR(i,1,m) g.addedge(n+i,n+m+i,1,0);    
}
void process(void) {
    assert(g.maxflow(2*(n+m)+1,2*(n+m+1))==n);
    FOR(i,1,m) res[i]=ii(0,0);
    FOR(i,1,n) {
        FORE(it,fth[i]) if (g.flow[it->se]>0) res[it->fi].fi=i;
        FORE(it,fsp[i]) if (g.flow[it->se]>0) res[it->fi].se=i;
    }
    FOR(i,1,m) printf("%d %d\n",res[i].fi,res[i].se);
}
int main(void) {
#ifndef ONLINE_JUDGE
    freopen("tmp.txt","r",stdin);
#endif  
    init();
    process();
}