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 <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

struct HopcroftKarp
{
    vector <int> leftMatch, rightMatch, dist, cur;
    vector < vector <int> > a;
    int m, n;

    HopcroftKarp() {}
    HopcroftKarp(int _m, int _n)
    {
        m = _m; n = _n;
        a = vector < vector <int> >(m);
        leftMatch = vector <int>(n, -1);
        rightMatch = vector <int>(m, -1);
        dist = vector <int>(m, -1);
        cur = vector <int>(m, -1);
    }

    void addEdge(int x, int y)
    {
        a[x].push_back(y);
    }

    int bfs()
    {
        int found = 0;
        queue <int> q;
        for (int i = 0; i < m; i++)
            if (rightMatch[i] < 0) dist[i] = 0, q.push(i);
            else dist[i] = -1;

        while (!q.empty())
        {
            int x = q.front(); q.pop();
            for (int i = 0; i < int(a[x].size()); i++)
            {
                int y = a[x][i];
                if (leftMatch[y] < 0) found = 1;
                else 
                    if (dist[leftMatch[y]] < 0)
                        dist[leftMatch[y]] = dist[x] + 1, q.push(leftMatch[y]);
            }
        }

        return found;
    }

    int dfs(int x)
    {
        for (; cur[x] < int(a[x].size()); cur[x]++)
        {
            int y = a[x][cur[x]];
            if (leftMatch[y] < 0 || (dist[leftMatch[y]] == dist[x] + 1 && dfs(leftMatch[y])))
            {
                leftMatch[y] = x; rightMatch[x] = y;
                return 1;
            }
        }
        return 0;
    }

    int maxMatching()
    {
        int match = 0;
        while (bfs())
        {
            for (int i = 0; i < m; i++) cur[i] = 0;
            for (int i = 0; i < m; i++) 
                if (rightMatch[i] < 0) match += dfs(i);
        }
        return match;
    }
};

int main()
{
    int m, n, edge, x, y;
    cin >> m >> n >> edge;
    HopcroftKarp u(m, n);
    while (edge--) scanf("%d%d", &x, &y), u.addEdge(--x, --y);
    cout << u.maxMatching() << endl;
}

Code mẫu của happyboy99x

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

const int N = 50000, INF = 1e9;
int mx[N], my[N], d[N], nx, ny;
vector<int> g[N];

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

bool dfs(int u, int mind) {
    for (int v : g[u]) if(my[v] == -1 ? d[u] == mind : d[my[v]] == d[u]+1 && dfs(my[v], mind)) return mx[u] = v, my[v] = u, true;
    d[u] = INF;
    return false;
}

int maxMatch() {
    int matching = 0;
    fill(mx, mx + nx, -1); fill(my, my + ny, -1);
    while(true) {
        fill(d, d + nx, INF); queue<int> q;
        for(int u = 0; u < nx; ++u) if(mx[u] == -1) d[u] = 0, q.push(u);
        int mind = INF;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) if(my[v] == -1) mind = min(mind, d[u]);
            else if(d[my[v]] == INF) d[my[v]] = d[u]+1, q.push(my[v]);
        }
        if(mind == INF) break;
        for(int u = 0; u < nx; ++u) if(d[u] > mind) d[u] = INF;
        for(int u = 0; u < nx; ++u)
            if(mx[u] == -1 && dfs(u, mind)) ++matching;
    }
    return matching;
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    cout << maxMatch() << endl;
    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, p; cin >> m >> n >> p;
    BipartiteGraph G(m, n);
    int u, v;
    while (p--) {
        cin >> u >> v;
        G.addEdge(--u, --v, vector<int>());
    }
    cout << G.fastMatch() << endl;
    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 1
const int inf = 1000111;
struct Matching {
    int n;
    vector<int> matchL, matchR, dist;
    vector<bool> seen;
    vector< vector<int> > ke;

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

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

    bool bfs() {
        queue<int> qu;
        FOR(u,1,n) if (!matchL[u]) {
            dist[u] = 0;
            qu.push(u);
        } else dist[u] = inf;
        dist[0] = inf;

        while (!qu.empty()) {
            int u = qu.front(); qu.pop();
            for(__typeof(ke[u].begin()) v = ke[u].begin(); v != ke[u].end(); ++v) {
                if (dist[matchR[*v]] == inf) {
                    dist[matchR[*v]] = dist[u] + 1;
                    qu.push(matchR[*v]);
                }
            }
        }
        return dist[0] != inf;
    }

    bool dfs(int u) {
        if (u) {
            for(__typeof(ke[u].begin()) v = ke[u].begin(); v != ke[u].end(); ++v)
                if (dist[matchR[*v]] == dist[u] + 1 && dfs(matchR[*v])) {
                    matchL[u] = *v;
                    matchR[*v] = u;
                    return true;
                }
            dist[u] = inf;
            return false;
        }
        return true;
    }

    int match() {
        int res = 0;
        while (bfs()) {
            FOR(u,1,n)
                if (!matchL[u])
                    if (dfs(u)) ++res;
        }
        return res;
    }
};


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

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, k, u, v;
    scanf("%d %d %d", &n, &m, &k);
    hopkarp.init(n, m);
    rep(i, k){
        scanf("%d %d", &u, &v);
        hopkarp.add(u, v);
    }
    printf("%d", hopkarp.maxMatching());
}

Code mẫu của skyvn97

#include<cstdio>
#include<vector>
#include<queue>
#define MAX   50505
using namespace std;
const int INF=(int)1e7;
vector<int> g[MAX];
int matx[MAX];
int maty[MAX];
int d[MAX];
int m,n,p;
void loadgraph(void) {
    scanf("%d",&m);
    scanf("%d",&n);
    scanf("%d",&p);
    int i,u,v;
    for (i=1;i<=p;i=i+1) {
        scanf("%d",&u);
        scanf("%d",&v);
        g[u].push_back(v);
    }
}
bool BFS(void) {
    queue<int> q;
    while (!q.empty()) q.pop();
    int i,u,v;
    for (i=1;i<=m;i=i+1) {
        if (matx[i]==0) {
            d[i]=0;
            q.push(i);
        }
        else d[i]=INF;
    }
    d[0]=INF;
    while (!q.empty()) {
        u=q.front();q.pop();
        if (d[u]<d[0])
            for (i=0;i<g[u].size();i=i+1) {
                v=g[u][i];
                if (d[maty[v]]>=INF) {
                    d[maty[v]]=d[u]+1;
                    q.push(maty[v]);
                }
            }
    }
    return (d[0]<INF);
}
bool DFS(const int &u) {
    if (u==0) return (true);
    int i,v;
    for (i=0;i<g[u].size();i=i+1) {
        v=g[u][i];
        if (d[maty[v]]==d[u]+1)
            if (DFS(maty[v])) {
                matx[u]=v;
                maty[v]=u;
                return (true);
            }       
    }
    d[u]=INF;
    return (false);
}
void fastmatching(void) {
    int i;
    for (i=1;i<=m;i=i+1) matx[i]=0;
    for (i=1;i<=n;i=i+1) maty[i]=0;
    int res=0;
    while (BFS()) {
    //  printf("ok\n");
        for (i=1;i<=m;i=i+1)
            if (matx[i]==0)
                if (DFS(i)) res++;
        //printf("%d\n",res);
    }
    printf("%d",res);
}
int main(void) {
#ifndef ONLINE_JUDGE
    freopen("tmp.txt","r",stdin);
#endif
    loadgraph();
    fastmatching();
    return 0;
}

Code mẫu của khuc_tuan

#include <cstdio>
#include <cstring>
using namespace std;

struct List {
    int i;
    List * next;    
};

List cont[400000];
int ncont1, ncont2;

List * ke[50050];
List * keY[50050];

int M, N, nE;
int X[50050], Y[50050], Q[50050], levelX[50050], levelY[50050];
bool vs[50050];
int L, R, maxLevel, socap;

inline void addList( List * & p, int i, int & cn) {
    List * q = cont + ++cn;
    q->i = i;
    q->next = p;
    p = q;
}

bool bfs() {
    L = 1;
    R = 0;
    memset( levelX, 0, sizeof(levelX));
    memset( levelY, 0, sizeof(levelY));
    ncont2 = 155000;
    memset( keY, 0, sizeof(keY));

    for(int i=1;i<=M;++i) if(X[i]==0) Q[++R] = i, levelX[i] = 1;
    maxLevel = 1000000;
    while(L<=R) {
        int u = Q[L++];
        if(levelX[u] > maxLevel) break;
        for(List * p = ke[u]; p!=NULL; p = p->next) {
            int v = p->i;
            if(levelY[v]==0) {
                levelY[v] = levelX[u] + 1;
                if(Y[v]==0)
                    maxLevel = levelY[v];
                else 
                    if(levelX[Y[v]]==0) {
                        levelX[Y[v]] = levelY[v] + 1;
                        Q[++R] = Y[v];
                    }
            }
            if(levelY[v] == levelX[u] + 1) addList( keY[v], u, ncont2);
        }
    }
    return maxLevel < 1000000;
}

bool dfs(int j) {
    for(List * p = keY[j]; p!=NULL; p = p->next) {
        int i = p->i;
        if(!vs[i]) {
            vs[i] = true;
            if(levelX[i]==1 || dfs(X[i])) {
                X[i] = j;
                Y[j] = i;
                return true;
            }
        }
    }
    return false;
}

void tang() {
    memset( vs, 0, sizeof(vs));
    for(int i=1;i<=N;++i) 
        if(levelY[i]==maxLevel && Y[i]==0)
            if(dfs(i)) ++socap;
}

int main() {
    scanf("%d%d%d", &M, &N, &nE);
    for(int i=0;i<nE;++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        if(X[u]==0 && Y[v]==0) {
            X[u] = v;
            Y[v] = u;
            ++socap;
        }
        addList( ke[u], v, ncont1);
    }   
    while(bfs()) tang();
    printf("%d\n", socap);
    return 0;
}