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 ladpro98

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

const int INF = 1e9;

struct BipartiteGraph {
    vector<vector<int> > c; // cost matrix
    vector<int> fx, fy; // potentials
    vector<int> matchX, matchY; // corresponding vertex
    vector<int> trace; // last vertex from the left side
    vector<int> d, arg; // distance from the tree && the corresponding node
    queue<int> Q; // queue used for BFS

    int n; // assume that |L| = |R| = n
    int start; // current root of the tree
    int finish; // leaf node of the augmenting path

    BipartiteGraph(int n) {
        this->n = n;
        c = vector<vector<int> >(n + 1, vector<int>(n + 1, INF));
        fx = fy = matchX = matchY = trace = d = arg = vector<int>(n + 1);
    }

    void addEdge(int u, int v, int cost) { c[u][v] = min(c[u][v], cost); }
    int cost(int u, int v) { return c[u][v] - fx[u] - fy[v]; }

    void initBFS(int root) {
        start = root;
        Q = queue<int>(); Q.push(start);
        for (int i = 1; i <= n; ++i) {
            trace[i] = 0;
            d[i] = cost(start, i);
            arg[i] = start;
        }
    }

    int findPath() {
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            for (int v = 1; v <= n; ++v) if (trace[v] == 0) {
                int w = cost(u, v);
                if (w == 0) {
                    trace[v] = u;
                    if (matchY[v] == 0) return v;
                    Q.push(matchY[v]);
                }
                if (d[v] > w) d[v] = w, arg[v] = u;
            }
        }
        return 0;
    }

    void enlarge() {
        for (int y = finish, next; y; y = next) {
            int x = trace[y];
            next = matchX[x];
            matchX[x] = y;
            matchY[y] = x;
        }
    }

    void update() {
        int delta = INF;
        for (int i = 1; i <= n; ++i) if (trace[i] == 0) delta = min(delta, d[i]);
        fx[start] += delta;
        for (int i = 1; i <= n; ++i) {
            if (trace[i] != 0) {
                fx[matchY[i]] += delta;
                fy[i] -= delta;
            } else {
                d[i] -= delta;
                if (d[i] == 0) {
                    trace[i] = arg[i];
                    if (matchY[i] == 0)
                        finish = i;
                    else
                        Q.push(matchY[i]);
                }
            }
        }
    }

    void hungarian() {
        for (int i = 1; i <= n; ++i) {
            initBFS(i);
            do {
                finish = findPath();
                if (finish == 0) update();
            } while (finish == 0);
            enlarge();
        }
    }

    void show() {
        int ans = 0;
        for (int i = 1; i <= n; ++i) if (matchX[i]) ans += c[i][matchX[i]];
        cout << ans << endl;
        for (int i = 1; i <= n; ++i) cout << i << ' ' << matchX[i] << endl;
    }
};

int main() {
    ios::sync_with_stdio(false);
    int n; cin >> n;
    BipartiteGraph G (n);
    int u, v, c;
    while (cin >> u >> v >> c) G.addEdge(u, v, c);
    G.hungarian();
    G.show();
    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;
const int maxn = 1007;
const int inf = 1000111000;

// Vertex: 1 --> nx, 1 --> ny
// cost >= 0
// fx[x] + fy[y] <= cost[x][y] for all x, y

struct Hungary {
    int nx, ny, cost[maxn][maxn], fx[maxn], fy[maxn], maty[maxn], which[maxn], dist[maxn];
    bool used[maxn];

    void init(int _nx, int _ny) {
        nx = _nx; ny = _ny;
        memset(fx, 0, sizeof fx);
        memset(fy, 0, sizeof fy);
        for(int i=0; i<=nx; ++i) for(int j=0; j<=ny; ++j) cost[i][j] = inf;
    }

    void add(int x, int y, int c) { cost[x][y] = min(cost[x][y],c); }

    int mincost() {
        for(int x=1; x<=nx; ++x) {
            int y0 = 0; maty[0] = x;
            for(int y=0; y<=ny; ++y) { dist[y] = inf + 1; used[y] = false; }

            do {
                used[y0] = true;
                int x0 = maty[y0], delta = inf + 1, y1;

                for(int y=1; y<=ny; ++y) if (!used[y]) {
                    int curdist = cost[x0][y] - fx[x0] - fy[y];
                    if (curdist < dist[y]) {
                        dist[y] = curdist;
                        which[y] = y0;
                    }
                    if (dist[y] < delta) {
                        delta = dist[y];
                        y1 = y;
                    }
                }

                for(int y=0; y<=ny; ++y) if (used[y]) {
                    fx[maty[y]] += delta;
                    fy[y] -= delta;
                } else dist[y] -= delta;

                y0 = y1;
            } while (maty[y0] != 0);

            do {
                int y1 = which[y0];
                maty[y0] = maty[y1];
                y0 = y1;
            } while (y0);
        }
//      return -fy[0]; // nếu luôn đảm bảo có bộ ghép đầy đủ
        int ret = 0;
        for(int y=1; y<=ny; ++y) {
            int x = maty[y];
            if (cost[x][y] < inf) ret += cost[x][y];
        }
        return ret;
    }
} hungary;


int m,n,e;

int main() {
    //freopen("input.txt","r",stdin);
    scanf("%d",&m); n=m;
    hungary.init(m,n);
    int x,y,w;
    while(scanf("%d%d%d",&x,&y,&w)!=EOF) hungary.add(y,x,w);
    printf("%d\n",hungary.mincost());
    for(int y=1; y<=hungary.ny; ++y){
        int x=hungary.maty[y];
        if(hungary.cost[x][y] < inf) printf("%d %d\n",y,x);
    }
}

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#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>
//#include<conio.h>
#define oo 1111111111
#define MAX 222

using namespace std;

int n,cuoi,c[MAX][MAX];
int fx[MAX],fy[MAX],mx[MAX],my[MAX],q[MAX],x[MAX],y[MAX],tr[MAX];

int cothe(int s){
     int dau = 0,cuo = 0,u,v;
     memset(x,0,sizeof(x));
     memset(y,0,sizeof(y));
     memset(tr,0,sizeof(tr));

     q[cuo++] = s;
     while(dau!=cuo){
           u = q[dau++]; x[u] = 1;
           for(v = 1;v<=n;v++)
                if(!y[v]&& c[u][v]==fx[u]+fy[v]){
                      y[v] = 1; tr[v] = u;
                      if(!my[v]) {cuoi = v; return true;}
                      q[cuo++] = my[v];
                }
     }
     return false;
}

void dao(){
      int delta = oo;
      for(int u = 1;u<=n;u++) if(x[u])
           for(int v = 1;v<=n;v++) if(!y[v]) delta = min(delta,c[u][v]-fx[u]-fy[v]);
      for(int i = 1;i<=n;i++) if(x[i]) fx[i]+=delta;
      for(int i = 1;i<=n;i++) if(y[i]) fy[i]-=delta;
}

void rong(int s){
      int u,v = cuoi,t;
      while(!mx[s]){
            u = tr[v];
            t = mx[u];
            my[v] = u; mx[u] = v;
            v = t;
          //  printf("?");
      }
}

int main(){
     // freopen("MATCH2.in","r",stdin);
      scanf("%d",&n);
      for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++) c[i][j] = oo;
      int a,b,d,kq = 0;
      while(scanf("%d %d %d",&a,&b,&d)>0){
           c[a][b] = min(c[a][b],d);
      }
      for(int i = 1;i<=n;i++){
          // printf("%d\n",i);
           while(!cothe(i)) dao();
          // printf("%d\n",i);
           rong(i);
      }
      for(int i = 1;i<=n;i++) kq+= fx[i]+fy[i];
      printf("%d\n",kq);
      for(int i = 1;i<=n;i++) printf("%d %d\n",i,mx[i]);
     // getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
program Finding_the_Best_Assignment;
const
  InputFile  = '';
  OutputFile = '';
  max = 200;
  maxEC = 200;
  maxC = max * maxEC + 1;
var
  c: array[1..max, 1..max] of Integer;
  Fx, Fy, matchX, matchY: array[1..max] of Integer;
  Trace, Queue, d, arg: array[1..max] of Integer;
  Front, Rear: Integer;
  start, finish: Integer;
  m, n, k: Integer;

procedure Enter;
var
  i, j: Integer;
  f: Text;
begin
  Assign(f, InputFile); Reset(f);
  ReadLn(f, n);
  k := n;
  m := n;
  for i := 1 to k do
    for j := 1 to k do c[i, j] := maxC;
  while not Eof(f) do ReadLn(f, i, j, c[i, j]);
  Close(f);
end;

procedure Init;
begin
  FillChar(matchX, SizeOf(matchX), 0);
  FillChar(matchY, SizeOf(matchY), 0);
  FillChar(Fx, SizeOf(Fx), 0);
  FillChar(Fy, SizeOf(Fy), 0);
end;

function GetC(i, j: Integer): Integer;
begin
  GetC := c[i, j] - Fx[i] - Fy[j];
end;

procedure InitBFS;
var
  j: Integer;
begin
  Front := 1; Rear := 1;
  Queue[1] := start;
  FillChar(Trace, SizeOf(Trace), 0);
  for j := 1 to k do
    begin
      d[j] := GetC(start, j);
      arg[j] := start;
    end;
  finish := 0;
end;

procedure Push(v: Integer);
begin
  Inc(Rear); Queue[Rear] := v;
end;

function Pop: Integer;
begin
  Pop := Queue[Front]; Inc(Front);
end;

procedure FindAugmentingPath;
var
  i, j, w: Integer;
begin
  repeat
    i := Pop;
    for j := 1 to k do
      if Trace[j] = 0 then
        begin
          w := GetC(i, j);
          if w = 0 then
            begin
              Trace[j] := i;
              if matchY[j] = 0 then
                begin
                  finish := j;
                  Exit;
                end;
              Push(matchY[j]);
            end;
          if d[j] > w then
            begin
              d[j] := w;
              arg[j] := i;
            end;
        end;
  until Front > Rear;
end;

procedure SubX_AddY;
var
  Delta: Integer;
  i, j: Integer;
begin
  Delta := maxC;
  for j := 1 to k do
    if (Trace[j] = 0) and (d[j] < Delta) then Delta := d[j];
  Fx[start] := Fx[start] + Delta;
  for j := 1 to k do
    if Trace[j] <> 0 then
      begin
        i := matchY[j];
        Fy[j] := Fy[j] - Delta;
        Fx[i] := Fx[i] + Delta;
      end
    else
      d[j] := d[j] - Delta;
  for j := 1 to k do
    if (Trace[j] = 0) and (d[j] = 0) then
      begin
        Trace[j] := arg[j];
        if matchY[j] = 0 then
          begin
            finish := j;
            Exit;
          end;
        Push(matchY[j]);
      end;
end;

procedure Enlarge;
var
  i, next: Integer;
begin
  repeat
    i := Trace[finish];
    next := matchX[i];
    matchX[i] := finish;
    matchY[finish] := i;
    finish := Next;
  until finish = 0;
end;

procedure Solve;
var
  i: Integer;
begin
  for i := 1 to k do
    begin
      start := i;
      InitBFS;
      repeat
        FindAugmentingPath;
        if finish = 0 then SubX_AddY;
      until finish <> 0;
      Enlarge;
    end;
end;

procedure Result;
var
  i, j, Count, W: Integer;
  f: Text;
begin
  Assign(f, OutputFile); Rewrite(f);

  W := 0; Count := 0;
  for i := 1 to m do
    begin
      j := matchX[i];
      W := W + c[i, j];
    end;

  WriteLn(f, W);
  for i := 1 to m do
    begin
      j := matchX[i];
      writeln(f, i, ' ', j);
    end;
  Close(f);
end;

begin
  Enter;
  Init;
  Solve;
  Result;
end.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   211
using namespace std;
const int INF=(int)1e9;
int c[MAX][MAX];
int t[MAX];
int d[MAX];
int fx[MAX];
int fy[MAX];
int matx[MAX];
int maty[MAX];
int argu[MAX];
int n,sta,fin;
queue<int> q;
void minimize(int &x,const int &y) {
    if (x>y) x=y;
}
void loadgraph(void) {
    int i,j,u,v;
    scanf("%d",&n);
    for (i=1;i<=n;i=i+1)
        for (j=1;j<=n;j=j+1)
            c[i][j]=INF;
    while (scanf("%d",&u)==1) {
        scanf("%d",&v);
        scanf("%d",&j);
        minimize(c[u][v],j);
    }
    for (i=1;i<=n;i=i+1) {
        fx[i]=INF;
        for (j=1;j<=n;j=j+1) minimize(fx[i],c[i][j]);
    }
    for (i=1;i<=n;i=i+1) {
        fy[i]=INF;  
        for (j=1;j<=n;j=j+1) minimize(fy[i],c[j][i]-fx[j]);
    }
    memset(matx,0,sizeof matx);
    memset(maty,0,sizeof maty);
}
int cost(const int &i,const int &j) {
    return (c[i][j]-fx[i]-fy[j]);
}
void init_BFS(void) {
    while (!q.empty()) q.pop();
    memset(t,0,sizeof t);
    int i,v;
    q.push(sta);
    for (i=1;i<=n;i=i+1) {
        d[i]=cost(sta,i);
        argu[i]=sta;
    }
    fin=0;
}
void findway(void) {
    int u,i,w;
    while (!q.empty()) {
        u=q.front();q.pop();
        for (i=1;i<=n;i=i+1)
            if (t[i]==0) {
                w=cost(u,i);
                if (w==0) {
                    t[i]=u;
                    if (maty[i]==0) {
                        fin=i;
                        return;
                    }
                    else q.push(maty[i]);
                }
                if (d[i]>w) {
                    d[i]=w;
                    argu[i]=u;
                }
            }
    }
}
void modify(void) {
    int i,j;
    int del;
    del=INF;
    for (i=1;i<=n;i=i+1)
        if (t[i]==0) minimize(del,d[i]);
    fx[sta]+=del;
    for (i=1;i<=n;i=i+1) {
        if (t[i]!=0) {
            j=maty[i];
            fx[j]+=del;
            fy[i]-=del;
        }
        else d[i]-=del;
    }
    for (i=1;i<=n;i=i+1)
        if (t[i]==0 && d[i]==0) {
            t[i]=argu[i];
            if (maty[i]==0) {
                fin=i;
                return;
            }
            else q.push(maty[i]);
        }
}
void enlarge(void) {
    int u,v;
    do {
        u=t[fin];
        v=matx[u];
        matx[u]=fin;
        maty[fin]=u;
        fin=v;
    }
    while (fin!=0);
}
void maxmatching(void) {
    int i;
    for (i=1;i<=n;i=i+1) {
        sta=i;
        init_BFS();
        do {
            findway();
            if (fin==0) modify();
        }
        while (fin==0);
        enlarge();
    }
    int r=0;
    for (i=1;i<=n;i=i+1)
        if (c[i][matx[i]]<INF) r+=c[i][matx[i]];
    printf("%d\n",r);
    for (i=1;i<=n;i=i+1) printf("%d %d\n",i,matx[i]);
}
int main(void) {
    loadgraph();
    maxmatching();
    return 0;
}

Code mẫu của khuc_tuan

#include "stdio.h"
#include "string.h"

#define maxc 500000

    typedef int mang[201];
    int n;      
    mang fx,fy,x,y,bx,by,q;
    int a[201][201];

    void nhap() {
        scanf("%d",&n);
        for(int i=0;i<201;++i) for(int j=0;j<201;++j) a[i][j]=maxc;
        while(true) {
            int u,v,c=9999;
            scanf("%d%d%d",&u,&v,&c);
            if(c==9999) break;
            a[u][v]=c;
        }
    }

    void tangcap(int v) {
        int u,k;
        while(v>0) {
            u=by[v];
            k=x[u];
            x[u]=v;
            y[v]=u;
            v=k;
        }
    }

    bool bfs(int i) {
        int L,R;
        q[L=R=1]=i;
        memset( by, 0, sizeof(by));
        memset( bx, 0, sizeof(bx));
        bx[i]=1;
        while(L<=R) {
            int u=q[L++];
            for(int v=1;v<=n;++v) if(by[v]==0 && fx[u]+a[u][v]-fy[v]==0) {
                by[v]=u;
                if(y[v]==0) {
                    tangcap(v);
                    return true;
                }
                q[++R]=y[v];
                bx[y[v]]=1;
            }
        }
        return false;
    }

    void suanhan() {
        int dt=maxc;
        for(int i=1;i<=n;++i) if(bx[i]==1)
            for(int j=1;j<=n;++j) if(by[j]==0)
                if(dt>fx[i]+a[i][j]-fy[j]) dt=fx[i]+a[i][j]-fy[j];
        for(int i=1;i<=n;++i) if(bx[i]==0) fx[i]+=dt;
        for(int i=1;i<=n;++i) if(by[i]==0) fy[i]+=dt;
    }

    void xuly() {
        for(int i=1;i<=n;++i) {
            while(!bfs(i)) suanhan();
        }
        int res=0;
        for(int i=1;i<=n;++i) res+=a[i][x[i]];
        printf("%d\n",res);
        for(int i=1;i<=n;++i) printf("%d %d\n",i,x[i]);
    }

int main() {
    nhap();
    xuly();
    return 0;
}