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>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define frr(a,b,c) for (a=b;a>=c;a--)
using namespace std;
int m,n,a[1111],b[1111],d[1111],c[1111][1111],t;   

int dfs(int x)
{
    int i;
    fr(i,1,n) 
       if (c[x][i] && !d[i])
       {
          t=i; d[i]=x;       
          if (!b[i] || dfs(b[i])) return 1;
       }
    return 0;
}

int find()
{
    int i;
    fr(i,1,n) d[i]=0;
    fr(i,1,m) 
      if (!a[i])
        if (dfs(i)) return 1;
    return 0;
}

void inc()
{
     int x,y;
     while (t)
     {
           x=d[t]; y=t;
           t=a[x]; a[x]=y; b[y]=x;           
     }
}

int main()
{
    int i,x,y,k,re=0;
    cin >> m >> n >> k;
    while (k--)
    {
          scanf("%d%d",&x,&y);
          c[x][y]=1; 
    }
    while (find()) inc();
    fr(i,1,m)
       if (a[i]) re++;
    cout << re << endl;
    return 0;
}

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)
#define mset(a,i) memset(a, i, sizeof a)
const int N = 1000;
int nx, ny, my[N], vy[N];
vector<int> g[N];

void enter() {
    cin >> nx >> ny; int m; cin >> m;
    for(int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        g[u-1].push_back(v-1);
    }
}

bool dfs(int s) {
    TR(g[s], u) if(!vy[*u]) {
        vy[*u] = true;
        if(my[*u] == -1 || dfs(my[*u])) return my[*u] = s, true;
    }
    return false;
}

int maxMatch() {
    mset(my, -1); int res = 0;
    for(int i = 0; mset(vy, 0), i < nx; ++i) if(dfs(i)) ++res;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    cout << maxMatch() << '\n';
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 1010;
using namespace std;
int matchX[N], matchY[N], Q[N], T[N];
int m, n, e;
vector<int> a[N];

int BFS() {
    int l = 1, r = 0, i, u, v;
    for(i = 1; i <= m; i++)
        if (matchX[i] == 0) Q[++r] = i;
    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) {
                T[v] = u;
                if (matchY[v] == 0) return v;
                else Q[++r] = matchY[v];
            }
        }
    }
    return 0;
}

void Enlarge(int y) {
    int next, x;
    for(; y; y = next) {
        x = T[y];
        next = matchX[x];
        matchX[x] = y;
        matchY[y] = x;
    }
}

int main() {
    scanf("%d %d %d", &m, &n, &e);
    int i, u, v;
    for(i = 1; i <= e; i++) {
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
    }
    while (i = BFS()) Enlarge(i);
    int res = 0;
    for(i = 1; i <= m; i++) if (matchX[i] != 0) res++;
    printf("%d\n", res);
}

Code mẫu của RR

const
  MAXN=1011;
type
  list=^node;
  node=record
        u:longint;
        next:list;
  end;

procedure add(u:longint; var a:list);
    var
      p:list;
    begin
      new(p); p^.u:=u;
      p^.next:=a; a:=p;
    end;

var
  n,m,k,u,v,x,y:longint;
  ke:array[1..MAXN] of list;
  matchX,matchY,trace,queue:array[1..MAXN] of longint;

function findPath(x:longint):longint;
    var
      u,v,first,last:longint;
      p:list;
    begin
      fillchar(trace,sizeof(trace),0);
      first:=1; last:=1; queue[1]:=x;
      while first<=last do
        begin
          u:=queue[first]; inc(first);
          p:=ke[u];
          while p<>nil do
            begin
              v:=p^.u; p:=p^.next;
              if (trace[v]=0) and (matchY[v]<>u) then
                begin
                  trace[v]:=u;
                  if matchY[v]=0 then exit(v);
                  inc(last); queue[last]:=matchY[v];
                end;
            end;
        end;
      exit(0);
    end;

procedure enlarge(y:longint);
    var
      x,next:longint;
    begin
      while y<>0 do
        begin
          x:=trace[y];
          next:=matchX[x];
          matchX[x]:=y;
          matchY[y]:=x;
          y:=next;
        end;
    end;

begin
  read(n,m,k);
  for k:=1 to k do
    begin
      read(u,v);
      add(v,ke[u]);
    end;

  for x:=1 to n do
    begin
      y:=findPath(x);
      enlarge(y);
    end;

  y:=0;
  for x:=1 to n do
    if matchX[x]<>0 then inc(y);
  writeln(y);
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);
}
// 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(x, 1, nx) last[x] = -1, matx[x] = -1;
        FOR(y, 1, ny) maty[y] = -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, k;
    scanf("%d %d %d", &n, &m, &k);
    hopkarp.init(n, m);
    while(scanf("%d %d", &x, &y) > 0){
        hopkarp.add(x, y);
    }
    printf("%d\n", hopkarp.maxMatching());
    /*
    FOR(x, 1, n){
        int y = hopkarp.matx[x];
        if(y != -1) printf("%d %d\n", x, y);
    }
    */
}

Code mẫu của ll931110

program NKBM;
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,k: 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, k);
  for i := 1 to k 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);
  close(f);
end;

begin
  init;
  solve;
  printresult;
end.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   1111
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,p;
    scanf("%d",&m);
    scanf("%d",&n);
    scanf("%d",&p);
    for (i=1;i<=p;i=i+1) {
        scanf("%d",&u);
        scanf("%d",&v);
        gx[u].push_back(v);
    }
}
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);    
}
int main(void) {
    //freopen("tmp.txt","r",stdin);
    loadgraph();
    maxmatching();
    print();
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>

using namespace std;

int m, n, sc;
bool a[1111][1111], vs[1111];
int x[1111], y[1111];

bool tim(int i) {
    if(vs[i]) return false;
    vs[i] = true;
    for(int j=1;j<=n;++j) if(a[i][j]) {
        if(y[j]==0) {
            x[i] = j;
            y[j] = i;
            return true;
        }
        if(tim(y[j])) {
            x[i] = j;
            y[j] = i;
            return true;
        }
    }
    return false;
}

int main() {
    int u, v, socap=0;
    scanf("%d%d%d", &m, &n, &sc);
    for(int i=0;i<sc;++i) {
        scanf("%d%d", &u, &v);
        a[u][v] = true;
    }
    for(int i=1;i<=m;++i) {
        memset( vs, 0, sizeof(vs));
        if(tim(i)) ++socap;
    }
    cout << socap << endl;
    //system("pause");
    return 0;
}