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

var n,m,x,y,re,nq,i:longint;
    c,f:array[1..111,1..111] of longint;
    a,b,d,q:array[1..111] of longint;

function find(var u:longint):boolean;
var i:longint;
begin
     fillchar(d,sizeof(d),0);
     nq:=0;
     for i:=1 to m do
         if a[i]=0 then
         begin
              inc(nq);
              q[nq]:=i;
         end;
     i:=1;
     while i<=nq do
     begin
          x:=q[i]; inc(i);
          for y:=1 to n do
              if (d[y]=0) and (c[x][y]=1) then
              begin
                   d[y]:=x;
                   if b[y]=0 then
                   begin
                        u:=y; exit(true);
                   end;
                   inc(nq);
                   q[nq]:=b[y];
              end;
     end;
     find:=false;
end;

procedure incflow(y:longint);
var x,t:longint;
begin
     while y>0 do
     begin
          x:=d[y]; t:=y; y:=a[x];
          b[t]:=x; a[x]:=t;
     end;
end;

begin
     read(m,n);
     while not eof do
     begin
          read(x);
          if x<=0 then break;
          read(y);
          c[x][y]:=1;
     end;
     while find(i) do incflow(i);
     for i:=1 to m do
         if a[i]>0 then inc(re);
     writeln(re);
     for i:=1 to m do
         if a[i]>0 then writeln(i,' ',a[i]);
end.

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 = 100;
int nx, ny;
vector<int> g[N];

void enter() {
    cin >> nx >> ny;
    for(int u, v; cin >> u >> v; )
        g[u-1].push_back(v-1);
}

void maxmatch() {
    vector<int> matchX (nx, -1);
    vector<int> matchY (ny, -1);
    int mxmatch = 0;
    while(true) {
        vector<int> trace (ny, -1); queue<int> q;
        for(int i = 0; i < nx; ++i)
            if(matchX[i] == -1) q.push(i);
        int f = -1;
        for(bool stop = false; !stop && !q.empty(); ) {
            int u = q.front(); q.pop();
            TR(g[u], v) if(trace[*v] == -1) {
                trace[*v] = u;
                if(matchY[*v] == -1) {
                    stop = true; f = *v;
                    break;
                } else q.push(matchY[*v]);
            }
        }
        if(f == -1) break;
        do {
            int x = trace[f], next = matchX[x];
            matchX[x] = f; matchY[f] = x;
            f = next;
        } while(f != -1);
        ++mxmatch;
    }
    cout << mxmatch << '\n';
    for(int i = 0; i < nx; ++i) if(matchX[i] != -1)
        cout << i+1 << ' ' << matchX[i]+1 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    maxmatch();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

struct BipartiteGraph {
    vector<vector<int> > E;
    vector<vector<pair<int, int> > > a;
    vector<int> match;
    vector<int> edgeMatch;
    vector<bool> was;
    int m, n;

    BipartiteGraph(int m, int n) {
        this->m = m; this->n = n;
        E.clear();
        a.clear();
        a.resize(m);
        match.assign(n, -1);
        edgeMatch.assign(n, -1);
        was.assign(n, false);
    }

    void addEdge(int u, int v, vector<int> expression) {
        int index = E.size();
        a[u].push_back(make_pair(v, index));
        E.push_back(expression);
    }

    bool dfs(int u) {
        for (int i = 0; i < a[u].size(); ++i) {
            int v = a[u][i].first;
            if (was[v]) continue;
            was[v] = true;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                edgeMatch[v] = a[u][i].second;
                return true;
            }
        }
        return false;
    }

    int fastMatch() {
        vector<int> buffer;
        for (int i = 0; i < m; ++i) buffer.push_back(i);
        bool stop = false;
        int ans = 0;
        do {
            stop = true;
            for (int i = 0; i < n; ++i) was[i] = false;
            for (int i = (int)buffer.size() - 1; i >= 0; --i) {
                int u = buffer[i];
                if (dfs(u)) {
                    ++ans;
                    stop = false;
                    buffer[i] = buffer.back();
                    buffer.pop_back();
                }
            }
        } while (!stop);
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    int n, m; cin >> m >> n;
    BipartiteGraph G(m, n);
    int u, v;
    while (cin >> u >> v)
        G.addEdge(--u, --v, vector<int>());
    cout << G.fastMatch() << endl;
    for (int i = 0; i < n; ++i) if (G.match[i] != -1)
        cout << G.match[i] + 1 << ' ' << i + 1 << '\n';
    return 0;
}

Code mẫu của RR

#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;

// Index from 0
// Assume 2 sides have same number of vertices
struct Matching {
    int n;
    vector< vector<int> > ke;
    vector< bool > seen;
    vector< int > matchL, matchR;

    Matching(int n) : n(n), ke(n), seen(n, false), matchL(n, -1), matchR(n, -1) {
    }

    void addEdge(int u, int v) {
        ke[u].push_back(v);
    }

    bool bpm(int u) {
        for(__typeof(ke[u].begin()) v = ke[u].begin(); v != ke[u].end(); ++v) {
            if (seen[*v]) continue;
            seen[*v] = true;

            if (matchR[*v] < 0 || bpm(matchR[*v])) {
                matchL[u] = *v;
                matchR[*v] = u;
                return true;
            }
        }
        return false;
    }

    int match() {
        int res = 0;
        for(int i = 0; i < n; ++i) {
            for(int i = 0; i < n; ++i) seen[i] = false;
            if (bpm(i)) ++res;
        }
        return res;
    }
};

int main() {
    ios :: sync_with_stdio(false); cin.tie(NULL);
    int m, n;
    while (cin >> m >> n) {
        Matching match(max(m, n));
        int u, v;
        while (cin >> u >> v) {
            --u; --v;
            match.addEdge(u, v);
        }

        cout << match.match() << endl;
        for(int i = 0; i < m; ++i)
            if (match.matchL[i] >= 0)
                cout << i+1 << ' ' << match.matchL[i] + 1 << "\n";
    }
}

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);
}
// Dinic

#define maxn 50011
#define maxe 150111

struct HopcroftKarp{
    int nx, ny, E, adj[maxe], next[maxe], last[maxn],
    matx[maxn], maty[maxn], que[maxn], level[maxn], run[maxn];

    void init(int _nx, int _ny){
        nx = _nx; ny = _ny; E = 0;
        FOR(i, 1, nx) matx[i] = -1, last[i] = -1;
        FOR(i, 1, ny) maty[i] = -1;
    }  

    void add(int x, int y){
        adj[E] = y; next[E] = last[x]; last[x] = E++;
    }

    bool bfs(){
        bool found = false;
        int size = 0;
        FOR(x, 1, nx){
            if(matx[x] != -1) level[x] = -1;
            else{
                level[x] = 0;
                que[size++] = x;
            }
        }
        rep(i, size){
            for(int x = que[i], e = last[x]; e != -1; e = next[e]){
                int y = adj[e];
                if(maty[y] == -1) found = true;
                else if(level[maty[y]] == -1){
                    level[maty[y]] = level[x] + 1;
                    que[size++] = maty[y];
                }
            }
        }

        return found;
    }

    int dfs(int x){
        for(int &e = run[x]; e != -1; e = next[e]){
            int y = adj[e];
            if(maty[y] == -1 || ( level[maty[y]] == level[x] + 1 && dfs(maty[y]))){
                maty[y] = x;
                matx[x] = y;
                return 1;
            }
        } 
        return 0;
    }

    int maxMatching(){
        int total = 0;
        while(bfs()){
            FOR(x, 1, nx) run[x] = last[x];
            FOR(x, 1, nx) if(matx[x] == -1) total += dfs(x);
        }
        return total;
    }

} hopkarp;

int main(){
   // OPEN();
    int n, m, x, y;
    scanf("%d %d",&n, &m);
    hopkarp.init(n, m);
    while(scanf("%d %d", &x, &y) > 0){
        hopkarp.add(x, y);
    }
    printf("%d\n",hopkarp.maxMatching());
    FOR(x, 1, n){
        y = hopkarp.matx[x];
        if(y != -1) printf("%d %d\n",x,y);
    }
}

Code mẫu của ll931110

program MATCH1;
const
  input  = '';
  output = '';
  maxn = 1000;
var
  a: array[1..maxn,1..maxn] of boolean;
  mx,my: array[1..maxn] of integer;
  trace,queue: array[1..maxn] of integer;
  front,rear: integer;
  m,n: integer;

procedure init;
var
  f: text;
  i,u,v: integer;
begin
  fillchar(a, sizeof(a), false);
  assign(f, input);
    reset(f);

  readln(f, m, n);
  while not eof(f) do
    begin
      readln(f, u, v);
      a[u,v] := true;
    end;

  close(f);
end;

procedure push(x: integer);
begin
  inc(rear);
  queue[rear] := x;
end;

function FindPath: integer;
var
  i,j: integer;
begin
  fillchar(trace, sizeof(trace), 0);
  front := 1; rear := 0;
  for i := 1 to m do
    if mx[i] = 0 then push(i);

  while front <= rear do
    begin
      i := queue[front];
      inc(front);

      for j := 1 to n do
        if (trace[j] = 0) and a[i,j] and (mx[i] <> j) then
          begin
            trace[j] := i;
            if my[j] = 0 then exit(j);
            push(my[j]);
          end;
    end;

  FindPath := 0;
end;

procedure Enlarge(x: integer);
var
  y,z: integer;
begin
  repeat
    y := trace[x];
    z := mx[y];
    mx[y] := x;
    my[x] := y;
    x := z;
  until x = 0;
end;

procedure solve;
var
  fin: integer;
begin
  repeat
    fin := FindPath;
    if fin <> 0 then Enlarge(fin);
  until fin = 0;
end;

procedure printresult;
var
  f: text;
  i,c: integer;
begin
  c := 0;
  for i := 1 to m do
    if mx[i] <> 0 then inc(c);

  assign(f, output);
    rewrite(f);

    writeln(f, c);
    for i := 1 to m do
      if mx[i] <> 0 then writeln(f, i, ' ', mx[i]);
  close(f);
end;

begin
  init;
  solve;
  printresult;
end.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   111
using namespace std;
vector<int> gx[MAX];
int matx[MAX];
int maty[MAX];
int tx[MAX];
int ty[MAX];
int m,n;
queue<int> q;
void loadgraph(void) {
    int i,u,v;
    scanf("%d",&m);
    scanf("%d",&n);
    while (scanf("%d%d",&u,&v)==2) {
        gx[u].push_back(v);
     //   gy[v].push_back(u);
    }
}
int findway(const int &s) {
    memset(tx,0,sizeof tx);
    memset(ty,0,sizeof ty);
    while (!q.empty()) q.pop();
    q.push(s);
    int i,p,v;
    while (!q.empty()) {
        p=q.front();q.pop();
        for (i=0;i<gx[p].size();i=i+1) {
            v=gx[p][i];
            if (ty[v]==0 && matx[p]!=v) {
                ty[v]=p;
                if (maty[v]==0) return (v);
                else {
                    tx[maty[v]]=v;
                    q.push(maty[v]);
                }
            }
        }
    }
    return (0);
}
void enlarge(const int &f) {
    int u,v;
    u=ty[f];
    while (u!=0) {
        v=tx[u];
        matx[u]=0;
        maty[v]=0;
        u=ty[v];
    }
    v=f;
    u=ty[f];
    while (u!=0) {
        matx[u]=v;
        maty[v]=u;
        v=tx[u];
        u=ty[v];
    }
}
void maxmatching(void) {
    memset(matx,0,sizeof matx);
    memset(maty,0,sizeof maty);
    int i,t;
    bool cont;
    for (i=1;i<=m;i=i+1) {
        t=findway(i);
        if (t>0) enlarge(t);
    }
}
void print(void) {
    int i,c=0;
    for (i=1;i<=m;i=i+1) c=c+(matx[i]!=0);
    printf("%d\n",c);
    for (i=1;i<=m;i=i+1)
        if (matx[i]>0) printf("%d %d\n",i,matx[i]);
}
int main(void) {
    //freopen("tmp.txt","r",stdin);
    loadgraph();
    maxmatching();
    print();
    return 0;
}