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 maxn 444
using namespace std;
int n,c[maxn][maxn],a[maxn],b[maxn],d[maxn],q[maxn],mid,t;

int find()
{
    int i,nq=0,x,y;
    fr(i,1,n) d[i]=0;
    fr(i,1,n)
      if (!a[i])
      {
         nq++; q[nq]=i;
      }
    i=1;
    while (i<=nq)
    {
        x=q[i++];
        fr(y,1,n)  
          if (c[x][y]<=mid && !d[y])
          {
             d[y]=x;
             if (!b[y])
             {
                t=y; 
                return 1;
             }
             nq++; q[nq]=b[y];
          }
    }
    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,j,low=1000000,high=0,re,s;
    cin >> n;
    fr(i,1,n)
     fr(j,1,n)
     {
        scanf("%d",&c[i][j]);
        low=min(low,c[i][j]);
        high=max(high,c[i][j]);
     }
    while (low<=high)
    {
          mid=(low+high)/2;
          fr(i,1,n)
          {
             a[i]=0; b[i]=0;
          }
          while (find()) inc();
          s=0;
          fr(i,1,n)
            if (a[i]) s++;
          if (s==n)
          {
            high=mid-1; re=mid;
          }
          else low=mid+1;
    }
    cout << re << endl;
    return 0;    
}

Code mẫu của happyboy99x

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

#define mset(a,v) memset(a, v, sizeof a)
const int N = 200, INF = 1e9;
int g[N][N], n, my[N];
bool vy[N];

void enter() {
    cin >> n;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j) 
            cin >> g[i][j];
}

bool dfs(int s, int lim) {
    for(int u = 0; u < n; ++u) if(!vy[u] && g[s][u] <= lim) {
        vy[u] = true;
        if(my[u] == -1 || dfs(my[u], lim)) return my[u] = s, true;
    }
    return false;
}

int solve() {
    int l = 0, h = INF;
    while(l < h) {
        mset(my, -1); int mid = (l + h) / 2; bool ok = true;
        for(int i = 0; mset(vy, 0), i < n && ok; ++i) ok &= dfs(i, mid);
        if(ok) h = mid; else l = mid + 1;
    }
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    cout << solve() << endl;
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 202;
using namespace std;

int c[N][N], T[N], Q[N], matchX[N], matchY[N];
int n, res;

int BFS(int lim) {
    int l = 1, r = 0, i, u, v;
    for(i = 1; i <= n; i++) {
        if (matchX[i] == 0) Q[++r] = i;
        T[i] = 0;
    }
    while (l <= r) {
        u = Q[l++];
        for(v = 1; v <= n; v++)
        if (T[v] == 0 && c[u][v] <= lim) {
            T[v] = u;
            if (matchY[v] == 0) return v;
            Q[++r] = matchY[v];
        }
    }
    return 0;
}

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

bool ok(int lim) {
    int i, j;
    for(i = 1; i <= n; i++) matchX[i] = matchY[i] = 0;
    for(i = 1; i <= n; i++) for(j = 1; j <= n; j++)
    if (matchX[i] == 0 && matchY[j] == 0 && c[i][j] <= lim) {matchX[i] = j; matchY[j] = i;}
    else break;
    while (i = BFS(lim)) Enlarge(i);
    for(i = 1; i <= n; i++)
        if (matchX[i] == 0) return false;
    return true;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) scanf("%d", &c[i][j]);
    int l = 0, r = 1 << 20, m;
    while (l <= r) {
        m = l + r >> 1;
        if (ok(m)) {
            res = m; r = m - 1;
        }
        else
            l = m + 1;
    }
    printf("%d", res);
    return 0;
}

Code mẫu của RR

var
  l,r,res,mid,i,j,n:longint;
  a,c:array[1..222,1..222] of longint;
  trace,matchX,matchY,queue:array[1..222] of longint;

function findPath(x:longint):longint;
    var
      u,v,first,last:longint;
    begin
      fillchar(trace,sizeof(trace),0);
      first:=1; last:=1; queue[1]:=x;
      while first<=last do
        begin
          u:=queue[first]; inc(first);
          for v:=1 to n do
          if (trace[v]=0) and (matchY[v]<>u) and (c[u,v]=1) then
            begin
              trace[v]:=u;
              if matchY[v]=0 then exit(v);
              inc(last); queue[last]:=matchY[v];
            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;

function check(val:longint):boolean;
    var
      x,y:longint;
    begin
      fillchar(matchX,sizeof(matchX),0);
      fillchar(matchY,sizeof(matchY),0);
      for x:=1 to n do
      for y:=1 to n do
        if a[x,y]<=val then c[x,y]:=1
        else c[x,y]:=0;

      for x:=1 to n do
        begin
          y:=findPath(x);
          if y<>0 then enlarge(y);
        end;

      y:=0;
      for x:=1 to n do
        if matchX[x]<>0 then inc(y);
      exit(y=n);
    end;

begin
  read(n);
  for i:=1 to n do
  for j:=1 to n do
    read(a[i,j]);

  l:=1; r:=1000111; res:=1000111;
  while l<=r do
    begin
      mid:=(l+r) shr 1;
      if check(mid) then
        begin
          r:=mid-1;
          res:=mid;
        end
      else l:=mid+1;
    end;
  writeln(res);
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#define max 201


int n,T,matchX[max],matchY[max],Trace[max],tg[max][max],maxtg = 0;
bool a[max][max];
void Init();
void Solve();

void Enter()
{
     scanf("%d",&n);
     for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
        {
            scanf("%d",&tg[i][j]);
            if(tg[i][j]>maxtg)
                maxtg =tg[i][j];
        }
}

bool xuly(int k)
{
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
        {
            if(tg[i][j]<=k)
                 a[i][j] = true;
            else a[i][j] = false;
        }
     Init();
     Solve();
     int KQ = 0;
     for(int i = 1;i<=n;i++)
         if(matchX[i]!=0)
             KQ++;
     if(KQ == n) return true;
     return false;

}

void Init()
{
     for(int i = 1;i<max;i++)    matchX[i] = 0;
     for(int i = 1;i<max;i++)    matchY[i] = 0;
}

int findpath()
{
    int queue[max];
    int i,j,first,last;
    for(i = 0;i<max;i++)
        Trace[i] = 0;  
    last = 0;
    for(i = 1;i<=n;i++)
         if(matchX[i] == 0)
         {
              last++;
              queue[last] = i;
         }
    first = 1;
    while(first <= last)
    {
        i = queue[first]; first++;
        for(j = 1;j<=n;j++)
              if(Trace[j] == 0 && a[i][j] && matchX[i] != j)
              {
                    Trace[j] = i;
                    if(matchY[j] ==0)
                         return j;
                    last++;
                    queue[last] = matchY[j];
              }
    }
    return 0;                       
}

void enlarge(int f)
{
    int x,next;
    do
    {
         x = Trace[f];
         next = matchX[x];
         matchX[x] = f;
         matchY[f] = x;
         f = next;
    }while(f!=0);
}

void Solve()
{
     int finish;
     do
     {
         finish = findpath();
         if(finish!=0) enlarge(finish);
     }while(finish!=0);
}

int main()
{
    // freopen("MATCH1.in","r",stdin);
     //freopen("ASSIGN1.in","r",stdin);
     Enter();
     int u=0,v=maxtg,r;
     while(v-u>1)
     {
          r = (u+v)/2;
          if(xuly(r))
              v = r;
          else u = r;       
     }
     printf("%d",v);

     //for(int i = 1;i<=m;i++)
      //   if(matchX[i]!=0)
           //  printf("%d %d\n",i,matchX[i]);
     //getch();
}

Code mẫu của ll931110

program ASSIGN1;
const
  input  = '';
  output = '';
  maxn = 200;
  maxv = high(longint);
var
  a: array[1..maxn,1..maxn] of longint;
  n,res: longint;
  q,trace,matchx,matchy: array[1..maxn] of longint;

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

  readln(fi, n);
  for i := 1 to n do
    for j := 1 to n do read(fi, a[i,j]);

  close(fi);
end;

function FindPath(x: longint): longint;
var
  front,rear: longint;
  i,j: longint;
begin
  front := 1;  rear := 0;
  fillchar(trace, sizeof(trace), 0);

  for i := 1 to n do if matchx[i] = 0 then
    begin
      inc(rear);  q[rear] := i;
    end;

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

      for j := 1 to n do
        if (trace[j] = 0) and (a[i,j] <= x) and (matchy[j] <> i) then
          begin
            trace[j] := i;
            if matchy[j] = 0 then exit(j);
            inc(rear);  q[rear] := matchy[j];
          end;
    end;

  exit(0);
end;

procedure Enlarge(f: longint);
var
  x,next: longint;
begin
  repeat
    x := trace[f];
    next := matchx[x];
    matchx[x] := f;
    matchy[f] := x;
    f := next;
  until f = 0;
end;

function ok(x: longint): boolean;
var
  nm,fin: longint;
begin
  nm := 0;
  fillchar(matchx, sizeof(matchx), 0);
  fillchar(matchy, sizeof(matchy), 0);
  repeat
    fin := FindPath(x);
    if fin = 0 then break;
    inc(nm);
    Enlarge(fin);
  until false;

  ok := nm = n;
end;

procedure solve;
var
  inf,sup,med: longint;
begin
  inf := 0;
  sup := maxv;
  repeat
    med := (inf + sup) div 2;
    if ok(med) then
      begin
        res := med;
        sup := med - 1;
      end
    else inf := med + 1;
  until inf > sup;
end;

procedure printresult;
var
  fo: text;
begin
  assign(fo, output);
    rewrite(fo);
    writeln(fo, res);
  close(fo);
end;

begin
  init;
  solve;
  printresult;
end.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   211
using namespace std;
const int INF=INT_MAX;
int n;
vector<int> g[MAX];
int c[MAX][MAX];
int matx[MAX];
int maty[MAX];
int t[MAX];
int maxc,minc;
queue<int> q;
void minimize(int &x,const int &y) {
    if (x>y) x=y;
}
void maximize(int &x,const int &y) {
    if (x<y) x=y;
}
void init(void) {
    scanf("%d",&n);
    int i,j;
    maxc=-INF;
    minc=INF;
    for (i=1;i<=n;i=i+1)
        for (j=1;j<=n;j=j+1) {
            scanf("%d",&c[i][j]);
            maximize(maxc,c[i][j]);
            minimize(minc,c[i][j]);
        }
}
void loadgraph(const int &lim) {
    int i,j;
    for (i=1;i<=n;i=i+1) g[i].clear();
    for (i=1;i<=n;i=i+1)
        for (j=1;j<=n;j=j+1)
            if (c[i][j]<=lim) g[i].push_back(j);
}
int findway(const int &s) {
    while (!q.empty()) q.pop();
    int u,v,i;
    memset(t,0,sizeof t);
    q.push(s);
    while (!q.empty()) {
        u=q.front();q.pop();
        for (i=0;i<g[u].size();i=i+1) {
            v=g[u][i];
            if (t[v]==0 && v!=matx[u]) {
                t[v]=u;
                if (maty[v]==0) return (v);
                else q.push(maty[v]);
            }
        }
    }
    return (0);
}
void enlarge(int f) {
    int u,v;
    do {
        u=t[f];
        v=matx[u];
        matx[u]=f;
        maty[f]=u;
        f=v;
    }
    while (f!=0);
}
bool maxmatching(const int &lim) {
    loadgraph(lim);
    memset(matx,0,sizeof matx);
    memset(maty,0,sizeof maty);
    int i,t,r;
    for (i=1;i<=n;i=i+1) {
        t=findway(i);
        if (t!=0) enlarge(t);
    }
    r=0;
    for (i=1;i<=n;i=i+1) r+=(matx[i]!=0);
    return (r==n);
}
void process(void) {
    int l,m,r;
    l=minc;
    r=maxc;
    while (true) {
        if (l==r) {
            printf("%d",r);
            return;
        }
        if (r-l==1) {
            if (maxmatching(l)) printf("%d",l);
            else printf("%d",r);
            return;
        }
        m=(l+r)/2;
        if (maxmatching(m)) r=m;
        else l=m+1;
    }
}
int main(void) {
    //freopen("tmp.txt","r",stdin); 
    init();
    process();
    return 0;
}

Code mẫu của khuc_tuan

Uses math;
Const     inp = '';
          out = '';
          maxn = 1001;

Var       n,res,c    : longint;
          a    : array [1..maxn,1..maxn] of longint;
          mx,my,queue,trace  :     array [1..maxn] of longint;

procedure nhap;
var i,j : longint;
  begin
      assign(input,inp); reset(input);
      assign(output,out); rewrite(output);
      readln(n);
      for i := 1 to n do
        for j := 1 to n do
          begin
            read(a[i,j]);
            c := max(c,a[i,j]);
          end;
  end;

procedure khoitao(x : longint);
var i,j : longint;
  begin
      fillchar(mx,sizeof(mx),0);
      fillchar(my,sizeof(my),0);
      for i := 1 to n do
        for j := 1 to n do
          if (a[i,j]<=x) and (my[j]=0) then
            begin
                my[j] := i; mx[i] := j;
                break;
            end;
  end;

function timduongmo(x : longint) : longint;
var i,j,left,right : longint;
   begin
       fillchar(trace,sizeof(trace),0);
       left := 0; right := 0;
       for i := 1 to n do
         if mx[i]=0 then
           begin
               inc(right); queue[right] := i;
           end;
       while left < right do
         begin
             inc(left); i := queue[left];
             for j := 1 to n do
               if (a[i,j]<=x) and (trace[j]=0) then
                 begin
                     trace[j] := i;
                     if my[j]=0 then exit(j);
                     inc(right); queue[right] := my[j];
                 end;
         end;
       exit(0);
   end;

procedure morong(f : longint);
var next,x : longint;
  begin
      repeat
         x := trace[f];
         next := mx[x];
         mx[x] := f;
         my[f] := x;
         f := next;
      until f=0;
  end;

function check(x : longint) : boolean;
var i,j,f,dem : longint;
  begin
      khoitao(x);
      repeat
         f := timduongmo(x);
         if f = 0 then break;
         morong(f);
      until false;
      dem := 0;
      for i := 1 to n do
        if mx[i]<>0 then inc(dem);
      if dem=n then exit(true) else exit(false);
  end;

procedure main;
var d,mid : longint;
  begin
      d := 0;
      while d <= c do
        begin
          mid := (d+c) shr 1;
          if check(mid) then
            begin
                res := mid;
                c := mid-1;
            end
          else d := mid+1;
        end;
      writeln(res);
  end;

begin
    nhap;
    main;
end.