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 <algorithm>
#include <string>
#include <cstring>
#include <queue>
#define oo 1000000
using namespace std;

string a[111];
int m,n,c[222][222],f[222][222],S,T,d[222],v[222];

int augment()
{
    queue <int> q;
    for (int i=1;i<=T;i++) d[i]=0;
    d[S]=S; v[S]=oo; q.push(S);
    while (!q.empty())
    {
        int x=q.front(); q.pop();
        for (int i=1;i<=T;i++)
            if (!d[i])
            {
                if (f[x][i]<c[x][i])
                {
                    v[i]=min(v[x],c[x][i]-f[x][i]);
                    q.push(i); d[i]=x;
                    if (i==T) return 1;
                }
                else
                    if (f[i][x])
                    {
                        v[i]=min(v[x],f[i][x]);
                        q.push(i); d[i]=-x;
                        if (i==T) return 1;
                    }
            }
    }
    return 0;
}

void incFlow()
{
    int delta=v[T],y,x=T;
    while (x!=S)
    {
        y=x; x=d[y];
        if (x>0) f[x][y]+=delta;
        else x=-x, f[y][x]-=delta;
    }
}

int maxFlow(int val)
{
    for (int i=0;i<m;i++)
        for (int j=0;j<n;j++)
            c[i+1][j+m+1]=(a[i][j]=='1');
    S=n+m+1; T=S+1; 
    for (int i=1;i<=m;i++) c[S][i]=2;
    for (int i=1;i<=n;i++) c[m+i][T]=val;
    memset(f,0,sizeof(f));

    while (augment()) incFlow();

    int res=0;
    for (int i=1;i<=m;i++) res+=f[S][i];
    return res;
}

int main()
{
    cin >> m >> n;
    for (int i=0;i<m;i++) cin >> a[i];

    int low=1,high=m,ans;
    while (low<=high)
    {
        int mid=(low+high)/2;
        if (maxFlow(mid)==m*2) ans=mid, high=mid-1;
        else low=mid+1;
    }

    cout << ans << endl;
}

Code mẫu của ladpro98

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
const int N = 210;
using namespace std;
char str[N];
int c[N][N], f[N][N], Q[N], T[N];
vector<int> adj[N];
int m, n, s, t;

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

void IncFlow() {
    int v = t, u, delta;
    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;
    }
}

bool ok(int lim) {
    for(int i = m + 1; i <= m + n; i++)
        c[i][t] = lim;
    memset(f, 0, sizeof f);
    while (BFS()) IncFlow();
    int flow = 0;
    for(int i = 1; i <= m; i++)
        flow += f[s][i];
    return flow == m + m;
}

int main() {
    scanf("%d %d\n", &m, &n);
    s = m + n + 1; t = s + 1;
    for(int i = 1; i <= m; i++) {
        gets(str);
        for(int j = 0; j < n; j++)
        if (str[j] == '1') {
            c[i][m + j + 1] = 1;
            adj[i].push_back(m + j + 1);
            adj[m + j + 1].push_back(i);
        }
        adj[s].push_back(i);
    }
    for(int i = 1; i <= m; i++)
        c[s][i] = 2;
    for(int i = m + 1; i <= m + n; i++)
        adj[i].push_back(t);
    int l = 1, r = m + m, mid, res = r;
    while (l <= r) {
        mid = l + r >> 1;
        if (ok(mid)) {
            res = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    printf("%d", res);
    return 0;
}

Code mẫu của RR

//Written by RR
{$R-,Q-}
{$Mode objfpc}
{$inline on}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       555;

var
  f1,f2         :       text;
  m,n           :       longint;
  sumFl         :       longint;
  c,fl          :       array[0..MAXN,0..MAXN] of longint;
  queue,trace   :       array[0..MAXN] of longint;
  first,last    :       longint;

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

procedure inp;
    var
      i,j:longint;
      ch:char;
    begin
      readln(f1,m,n);
      for i:=1 to m do
        begin
          c[0,i]:=2;
          for j:=1 to n do
            begin
              read(f1,ch);
              if ch='1' then
                c[i,m+j]:=1;
            end;
          readln(f1);
        end;
    end;

function findPath:boolean;
    var
      u,v:longint;
    begin
      fillchar(trace,sizeof(trace),$FF);
      trace[0]:=0;
      first:=1; last:=1; queue[1]:=0;
      while first<=last do
        begin
          u:=queue[first]; inc(first);
          for v:=1 to m+n+1 do
            if (trace[v]=-1) and (fl[u,v]<c[u,v]) then
              begin
                trace[v]:=u;
                if v=m+n+1 then exit(true);
                inc(last); queue[last]:=v;
              end;
        end;
      exit(false);
    end;

procedure incFlow;
    var
      u,v,delta:longint;
    begin
      inc(sumFl);
      v:=m+n+1; delta:=high(longint);
      repeat
        u:=trace[v];
        delta:=min(delta,c[u,v]-fl[u,v]);
        v:=u;
      until v=0;
      v:=m+n+1;
      repeat
        u:=trace[v];
        fl[u,v]+=delta;
        fl[v,u]-=delta;
        v:=u;
      until v=0;
    end;

procedure solve;
    var
      res,i:longint;
    begin
      res:=0;
      repeat
        inc(res);
        for i:=m+1 to m+n do inc(c[i,m+n+1]);
        while findPath do incFlow;
      until sumFl=2*m;
      writeln(f2,res);
    end;

begin
  openF;
  inp;
  solve;
  closeF;
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 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 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);
}

#define maxn 1111
#define maxe 100111

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; string s[111];

bool thoaman(int x){
    dinic.init(0, n + m + 1);
    FOR(i, 1, n) dinic.add(0, i, 2, 0);
    FOR(i, n + 1, n + m) dinic.add(i, n + m + 1, x, 0);
    rep(i, n) rep(j, m) if(s[i][j] == '1'){
        dinic.add(i + 1, n + 1 + j, 1, 0);
    }

    if(dinic.maxflow() == 2 * n) return true;
    return false;
}

int main(){
   // OPEN();
    scanf("%d %d", &n, &m);
    rep(i, n) cin >> s[i];
    int u = 0, v = 111, r;
    while(u < v){
        r = (u + v) >> 1;
        if(thoaman(r)) v = r;
        else u = r + 1;
    }

    printf("%d", u);
}

Code mẫu của ll931110

{$MODE DELPHI}
program TWOBLACK;
const
  input  = '';
  output = '';
  maxn = 200 + 2;
  maxk = 100;
  maxv = 1000;
var
  m,n,s,t: integer;
  c,f: array[0..maxn,0..maxn] of integer;
  queue,trace: array[0..maxn] of integer;

procedure init;
var
  fi: text;
  i,j: integer;
  ch: char;
begin
  assign(fi, input);
    reset(fi);

  readln(fi, n, m);
  s := 0;
  t := 1 + m + n;

  fillchar(c, sizeof(c), 0);
  for i := 1 to n do c[s,i] := 2;

  for i := 1 to n do
    begin
      for j := 1 to m do
        begin
          read(fi, ch);
          if ch = '1' then c[i,n + j] := 1;
        end;
      readln(fi);
    end;

  close(fi);
end;

function findpath: boolean;
var
  front,rear: integer;
  u,v: integer;
begin
  for u := s to t do trace[u] := maxv;
  trace[0] := -1;

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

    for v := 0 to t do
      if (trace[v] = maxv) 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
  delta,u,v: 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 maxflow(k: integer);
var
  i: integer;
begin
  for i := 1 to m do c[n + i,t] := k;
  fillchar(f, sizeof(f), 0);

  repeat
    if not findpath then break;
    incflow;
  until false;
end;

procedure solve;
var
  fo: text;
  i,flow: integer;
  inf,sup,med,res: integer;
begin
  inf := 1;
  sup := maxk;

  repeat
    med := (inf + sup) div 2;
    maxflow(med);

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

    if flow = 2 * n then
      begin
        res := med;
        sup := med - 1;
      end
    else inf := med + 1;
  until inf > sup;

  assign(fo, output);
    rewrite(fo);
    writeln(fo, res);
  close(fo);
end;

begin
  init;
  solve;
end.

Code mẫu của khuc_tuan

//{$APPTYPE CONSOLE}

program chono8;     { version 8 }

const fin='';
      fout='';
      mnmax=100;

var f:text;
    a:array[1..mnmax,1..mnmax] of byte;
    b:array[1..mnmax] of boolean;
    c:array[1..mnmax] of byte;
    m,n:byte;

procedure nhap;
          var i,j:byte;
              c:char;
          begin
               assign(f,fin);
               reset(f);
               readln(f,m,n);
               for i:=1 to m do
                   begin
                        for j:=1 to n do
                            begin
                                 read(f,c);
                                 a[i,j]:=ord(c)-ord('0');
                            end;
                        readln(f);
                   end;
               close(f);
          end;

procedure chon_bua;
          var co:byte;
              i,j:byte;
          begin
               for i:=1 to m do
                   begin
                        co:=0;
                        for j:=1 to n do
                            if a[i,j]=1 then
                               begin
                                    a[i,j]:=2;
                                    inc(co);
                                    inc(c[j]);
                                    if co=2 then break;
                               end;
                   end;
          end;

function findmax:byte;
         var _re,i,m:byte;
         begin
              m:=0;
              for i:=1 to n do
                  if c[i]>m then
                     begin
                          m:=c[i];
                          _re:=i;
                     end;
              findmax:=_re;
         end;

function habac(i:byte):boolean;
         var _re:boolean;
             j,k:byte;
         begin
              for j:=1 to n do
                  if not b[j] and (j<>i) and (c[j]<c[i])then
                     for k:=1 to m do
                         if (a[k,i]=2) and (a[k,j]=1) then
                            begin
                                 a[k,i]:=1;
                                 dec(c[i]);
                                 a[k,j]:=2;
                                 inc(c[j]);
                                 b[j]:=true;
                                 _re:=true;
                                 if c[j]>c[i] then _re:=habac(j);
                                 if not _re then
                                    begin
                                         a[k,i]:=2;
                                         inc(c[i]);
                                         a[k,j]:=1;
                                         dec(c[j]);
                                         {b[j]:=false;}
                                    end
                                 else
                                     begin
                                          habac:=true;
                                          exit;
                                     end;
                            end;
              habac:=false;
         end;

procedure chinh_ly;
          var m:byte;
              ok:boolean;
              max:byte;
              i:byte;
          begin
               repeat
                     fillchar(b,sizeof(b),false);
                     m:=findmax;
                     max:=c[m];
                     b[m]:=true;
                     ok:=false;
                     for i:=1 to n do
                         if (c[i]=max) and habac(i) then
                            ok:=true;
               until not ok;
          end;

procedure xuly;
          begin
               chon_bua;
               chinh_ly;
          end;

procedure ghi;
          var i,j:byte;
          begin
               assign(f,fout);
               rewrite(f);
               writeln(f,c[findmax]);
{               for i:=1 to m do
                   begin
                        for j:=1 to n do
                            if a[i,j]=2 then write(f,'1') else write(f,'0');
                        writeln(f);
                   end;}
               close(f);
          end;

procedure mktest;
          var i,j:byte;
          begin
                assign(f,fin);
                rewrite(f);
                randomize;
                m:=100;
                n:=100;
                writeln(f,m,' ',n);
                for i:=1 to m do
                    begin
                         for j:=1 to n do
                             if random(20)=1 then write(f,'1') else write(f,'0');
                         writeln(f);
                    end;
                close(f);
          end;

begin
{     mktest;}
     nhap;
     xuly;
     ghi;
end.