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>
const int N = 1010;
const int oo = 1000000000;
using namespace std;
int c[N][N], Fx[N], Fy[N], L[N], R[N], Q[N], T[N], matchX[N], matchY[N], d[N], t[N];
int n, l, r, start, finish, ll, rr;

int getC(int u, int v) {return c[u][v] - Fx[u] - Fy[v];}

void InitBFS() {
    ll = rr = 1; Q[1] = start; finish = 0;
    for(int i = 1; i <= r; i++) {
        T[i] = 0;
        d[i] = getC(start, i);
        t[i] = start;
    }
}

int findPath() {
    int u, v, w;
    while (ll <= rr) {
        u = Q[ll++];
        for(v = 1; v <= r; v++)
        if (T[v] == 0) {
            w = getC(u, v);
            if (w == 0) {
                T[v] = u;
                if (matchY[v] == 0) return v;
                Q[++rr] = matchY[v];
            }
            if (d[v] > w) {
                d[v] = w; t[v] = u;
            }
        }
    }
    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;
    }
}

void subX_addY() {
    int delta = oo, i, j;
    for(i = 1; i <= r; i++) if (T[i] == 0 && d[i] < delta) delta = d[i];
    Fx[start] += delta;
    for(j = 1; j <= r; j++) if (T[j] != 0) {
        i = matchY[j];
        Fx[i] += delta; Fy[j] -= delta;
    }
    else d[j] -= delta;
    for(j = 1; j <= r; j++) if (T[j] == 0 && d[j] == 0) {
        T[j] = t[j];
        if (matchY[j] == 0) {finish = j; return;}
        Q[++rr] = matchY[j];
    }
}

int main()
{
    int test, i, j, ai;
    scanf("%d", &test);
    while (test--) {
        scanf("%d", &n);
        l = 0; r = 0;
        for(i = 1; i <= n; i++) {
            scanf("%d", &ai);
            for(j = 1; j <= ai - 1; j++) L[++l] = i;
            if (ai == 0) R[++r] = i;
        }
        for(i = 1; i <= l; i++) matchX[i] = 0;
        for(j = 1; j <= r; j++) matchY[j] = 0;
        for(i = 1; i <= l; i++) for(j = 1; j <= r; j++)
            c[i][j] = min(abs(L[i] - R[j]), n - abs(L[i] - R[j]));
        for(i = 1; i <= l; i++) Fx[i] = *min_element(c[i], c[i] + r);
        for(j = 1; j <= r; j++) Fy[j] = d[j] = T[j] = 0;
        for(i = 1; i <= l; i++) {
            start = i; InitBFS();
            do {
                finish = findPath();
                if (finish == 0) subX_addY();
            } while (finish == 0);
            Enlarge(finish);
        }
        int res = 0;
        for(i = 1; i <= l; i++) res += c[i][matchX[i]];
        printf("%d\n", res);
    }
    return 0;
}

Code mẫu của RR

{$R-,Q-}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=1001;
  oo=1000000000;
var
  f1,f2:text;
  test,t,n,m,k:longint;
  c:array[1..MAXN,1..MAXN] of longint;
  queue,vitri,matchX,matchY,trace,fx,fy:array[1..MAXN] of longint;
  visitedX,visitedY:array[1..MAXN] of boolean;
procedure openF; inline;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
  close(f1); close(f2);
end;
procedure inp; inline;
var
  i,j,u:longint;
begin
  read(f1,n); m:=0;
  for i:=1 to n do
    begin
      read(f1,u);
      for j:=1 to u do
        begin
          inc(m);
          vitri[m]:=i;
        end;
    end;
  k:=max(m,n);
  for i:=1 to m do
  for j:=1 to n do
    if vitri[i]=j then c[i,j]:=0
    else if vitri[i]<j then c[i,j]:=min(j-vitri[i],n-j+vitri[i])
    else {vitri[i]>j} c[i,j]:=min(vitri[i]-j,n-vitri[i]+j);
  for i:=m+1 to k do
  for j:=1 to k do
    c[i,j]:=oo;
end;
procedure init; inline;
var
  i,j:longint;
begin
  fillchar(matchX,sizeof(matchX),0);
  fillchar(matchY,sizeof(matchY),0);
  for i:=1 to k do
    begin
      fx[i]:=oo;
      for j:=1 to k do fx[i]:=min(fx[i],c[i,j]);
    end;
  for j:=1 to k do
    begin
      fy[j]:=oo;
      for i:=1 to k do fy[j]:=min(fy[j],c[i,j]-fx[i]);
    end;
end;
function findPath(start:longint):longint; inline;
var
  first,last,x,y:longint;
begin
  fillchar(visitedX,sizeof(visitedX),false);
  fillchar(visitedY,sizeof(visitedY),false);
  fillchar(trace,sizeof(trace),0);
  visitedX[start]:=true;
  first:=1; last:=1; queue[1]:=start;
  while first<=last do
    begin
      x:=queue[first]; inc(first);
      for y:=1 to k do
        if (not visitedY[y]) and (matchX[x]<>y) and (c[x,y]=fx[x]+fy[y]) then
          begin
            trace[y]:=x;
            if matchY[y]=0 then exit(y);
            visitedY[y]:=true;
            visitedX[matchY[y]]:=true;
            inc(last); queue[last]:=matchY[y];
          end;
    end;
  findPath:=0;
end;
procedure subX_addY; inline;
var
  x,y,delta:longint;
begin
  delta:=oo;
  for x:=1 to k do
  if visitedX[x] then
    for y:=1 to k do
    if not visitedY[y] then
      delta:=min(delta,c[x,y]-fx[x]-fy[y]);
  for x:=1 to k do
    if visitedX[x] then fx[x]:=fx[x]+delta;
  for y:=1 to k do
    if visitedY[y] then fy[y]:=fy[y]-delta;
end;
procedure enlarge(f:longint); inline;
var
  x,next:longint;
begin
  repeat
    x:=trace[f];
    next:=matchX[x];
    matchX[x]:=f;
    matchY[f]:=x;
    f:=next;
  until f=0;
end;
procedure solve;
var
  x,y:longint;
begin
  for x:=1 to k do
    begin
      repeat
        y:=findPath(x);
        if y=0 then subX_addY;
      until y<>0;
      enlarge(y);
    end;
end;
procedure ans;
var
  cost,x,y:longint;
begin
  cost:=0;
  for x:=1 to n do
    begin
      y:=matchX[x];
      if c[x,y]<oo then inc(cost,c[x,y]);
    end;
  writeln(f2,cost);
end;
begin
  openF;
  read(f1,t);
  for test:=1 to t do
    begin
      inp;
      init;
      solve;
      ans;
    end;
  closeF;
end.

Code mẫu của ll931110

program BOXES;
const
  input  = '';
  output = '';
  maxn = 1000;
  maxv = 2000000;
var
  k,n,nball,nhole: longint;

  a,trace,arg: array[1..maxn] of longint;
  Fx,Fy,matchX,matchY: array[1..maxn] of longint;
  free: array[1..maxn] of boolean;
  c: array[1..maxn,1..maxn] of longint;

  start,fin: longint;
  queue,d: array[1..maxn] of longint;
  front,rear: longint;

  i,nTest: longint;
  fi,fo: text;

procedure openfile;
begin
  assign(fi, input);
    reset(fi);

  assign(fo, output);
    rewrite(fo);
end;

procedure closefile;
begin
  close(fo);
  close(fi);
end;

procedure init;
var
  i,j,cc: longint;
begin
  readln(fi, n);
  for i := 1 to n do read(fi, a[i]);

  for i := 1 to n do
    for j := 1 to n do c[i,j] := maxv;

  fillchar(free, sizeof(free), true);
  nball := 0;

  nhole := n;
  for i := 1 to n do if a[i] > 0 then
    begin
      free[i] := false;
      dec(nhole);
    end;

  for i := 1 to n do if a[i] > 1 then
    while a[i] > 1 do
      begin
        inc(nball);

        cc := 1;
        j := i + 1;
        if j > n then j := j - n;

        while j <> i do
          begin
            if free[j] and (c[nball,j] > cc) then c[nball,j] := cc;
            inc(j);
            if j > n then j := j - n;
            inc(cc);
          end;

        cc := 1;
        j := i - 1;
        if j = 0 then j := n;

        while j <> i do
          begin
            if free[j] and (c[nball,j] > cc) then c[nball,j] := cc;
            dec(j);
            if j = 0 then j := n;
            inc(cc);
          end;

        dec(a[i]);
      end;

  k := n;

  fillchar(matchX, sizeof(matchX), 0);
  fillchar(matchY, sizeof(matchY), 0);
  fillchar(Fx, sizeof(Fx), 0);
  fillchar(Fy, sizeof(Fy), 0);
end;

procedure push(u: longint);
begin
  inc(rear);  queue[rear] := u;
end;

function pop: longint;
begin
  pop := queue[front];
  inc(front);
end;

function get(x,y: longint): longint;
begin
  get := c[x,y] - Fx[x] - Fy[y];
end;

procedure initBFS;
var
  j: longint;
begin
  front := 1;  rear := 1;
  queue[1] := start;
  fillchar(trace, sizeof(trace), 0);

  for j := 1 to k do
    begin
      d[j] := get(start,j);
      arg[j] := start;
    end;

  fin := 0;
end;

procedure FindPath;
var
  i,j,w: longint;
begin
  repeat
    i := pop;
    for j := 1 to k do
      if trace[j] = 0 then
        begin
          w := get(i,j);
          if w = 0 then
            begin
              trace[j] := i;
              if matchY[j] = 0 then
                begin
                  fin := 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,i,j: longint;
begin
  delta := maxv;
  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
            fin := j;
            exit;
          end;
        push(matchY[j]);
      end;
end;

procedure Enlarge;
var
  i,next: longint;
begin
  repeat
    i := trace[fin];
    next := matchX[i];
    matchX[i] := fin;
    matchY[fin] := i;
    fin := next;
  until fin = 0;
end;

procedure solve;
var
  i: longint;
begin
  for i := 1 to k do
    begin
      start := i;
      initBFS;

      repeat
        FindPath;
        if fin = 0 then SubX_AddY;
      until fin <> 0;

      Enlarge;
    end;
end;

procedure printresult;
var
  i,j,w: longint;
begin
  w := 0;
  for i := 1 to n do
    begin
      j := matchX[i];
      if c[i,j] < maxv then w := w + c[i,j];
    end;

  writeln(fo, w);
end;

begin
  openfile;

  readln(fi, nTest);
  for i := 1 to nTest do
    begin
      init;
      solve;
      printresult;
    end;

  closefile;
end.