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 N = 51;
const int M = N * N;
const int INF = 1e9;

int m, n, mn;

namespace Graph {
    int c[N][M], fx[N], fy[M], matchX[N], matchY[M], d[M], arg[M], trace[M];
    queue<int> Q;
    int start, finish;

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

    void init() {
        for (int i = 1; i <= m; ++i) for (int j = 1; j <= mn; ++j) c[i][j] = INF;
    }

    void initBFS(int root) {
        start = root;
        Q = queue<int>(); Q.push(start);
        for (int i = 1; i <= mn; ++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 <= mn; ++v) if (!trace[v]) {
                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 update() {
        int delta = INF;
        for (int i = 1; i <= mn; ++i) if (trace[i] == 0 && delta > d[i]) delta = d[i];
        fx[start] += delta;
        for (int i = 1; i <= mn; ++i) {
            if (trace[i]) {
                fx[matchY[i]] += delta;
                fy[i] -= delta;
            } else {
                d[i] -= delta;
                if (d[i] == 0) {
                    trace[i] = arg[i];
                    if (!matchY[i])
                        finish = i;
                    else
                        Q.push(matchY[i]);
                }
            }
        }
    }

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

    int hungarian() {
        for (int i = 1; i <= m; ++i) {
            initBFS(i);
            do {
                finish = findPath();
                if (finish == 0) update();
            } while (finish == 0);
            enlarge();
        }
        int ans = 0;
        for (int i = 1; i <= m; ++i) {
            ans += c[i][matchX[i]];
            if (ans >= INF) return -1;
        }
        return ans;
    }
}

int c[N];
char s[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> c[i];
    for (int i = 1; i <= n; ++i) cin >> (s[i] + 1);
    m = strlen(s[1] + 1);
    mn = m * n;
    Graph::init();
    for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) if (s[j][i] == 'Y')
        for (int k = 1; k <= m; ++k) Graph::c[i][(j - 1) * m + k] = c[j] * (2 * k - 1);
    cout << Graph::hungarian() << endl;
    return 0;
}

Code mẫu của RR

//Written by Nguyen Thanh Trung
//Lam duoc bai nay da chung to minh that la B-)
{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=111;
  oo=1000000001;
var
  f1,f2:text;
  inq,d,trace,queue,cost:array[0..MAXN] of longint;
  fl,c,now:array[0..MAXN,0..MAXN] of longint;
  target,m,n:longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
var
  i,j:longint;
  s:string;
  ch:char;
begin
  readln(f1,m);
  for i:=1 to m do read(f1,cost[i]); readln(f1);
  readln(f1,s); n:=length(s);
  for i:=1 to m do fl[0,i]:=n;
  target:=m+n+1;
  for i:=m+1 to m+n do fl[i,target]:=1;
  for i:=1 to n do
    if s[i]='Y' then fl[1,m+i]:=1;
  for i:=2 to m do
    begin
      for j:=1 to n do
        begin
          read(f1,ch);
          if ch='Y' then fl[i,m+j]:=m+n;
        end;
      readln(f1);
    end;
end;
procedure refine;
var
  i,j:longint;
  ok:boolean;
begin
  for j:=m+1 to m+n do
    begin
      ok:=false;
      for i:=1 to m do
        if fl[i,j]>0 then ok:=true;
      if not ok then
        begin
          writeln(f2,-1);
          closeF; halt;
        end;
    end;
end;
procedure findPath;
var
  first,last,spt,u,v:longint;
begin
  fillchar(trace,sizeof(trace),0);
  fillchar(inq,sizeof(inq),0);
  first:=1; last:=1; spt:=1; queue[1]:=0; d[0]:=0; inq[0]:=1;
  for u:=1 to target do d[u]:=oo;
  while spt>0 do
    begin
      u:=queue[first]; inc(first); if first>MAXN then first-=MAXN;
      inq[u]:=0; dec(spt);
      for v:=1 to target do
      if (fl[u,v]>now[u,v]) and (d[v]>d[u]+c[u,v]) then
        begin
          d[v]:=d[u]+c[u,v];
          trace[v]:=u;
          if inq[v]=0 then
            begin
              inq[v]:=1; inc(spt);
              inc(last); if last>MAXN then last-=MAXN; queue[last]:=v;
            end;
        end
      else if (now[v,u]>0) and (d[v]>d[u]-c[v,u]) then
        begin
          d[v]:=d[u]-c[v,u];
          trace[v]:=-u;
          if inq[v]=0 then
            begin
              inq[v]:=1; inc(spt);
              inc(last); if last>MAXN then last-=MAXN; queue[last]:=v;
            end;
        end;
    end;
end;
procedure enlarge;
var
  u,v,delta:longint;
begin
  delta:=oo;
  v:=target;
  repeat
    u:=trace[v];
    if u>=0 then delta:=min(delta,fl[u,v]-now[u,v])
    else delta:=min(delta,now[v,-u]);
    v:=abs(u);
  until v=0;
  v:=target;
  repeat
    u:=trace[v];
    if u>=0 then now[u,v]+=delta
    else now[v,-u]-=delta;
    v:=abs(u);
  until v=0;
end;
procedure init;
var
  i,j:longint;
begin
  for i:=1 to m do
  for j:=m+1 to m+n do
    c[i,j]:=cost[i]*(now[0,i]<<1+1);
end;
procedure solve;
begin
  repeat
    init;
    findPath;
    if trace[target]<>0 then enlarge;
  until trace[target]=0;
end;
procedure ans;
var
  i,sum:longint;
begin
  sum:=0;
  for i:=1 to m do
    sum+=now[0,i]*now[0,i]*cost[i];
  writeln(f2,sum);
end;
begin
  openF;
  inp;
  refine;
  solve;
  ans;
  closeF;
end.

Code mẫu của ll931110

program COST;
const
  input  = '';
  output = '';
  maxn = 50;
  maxk = 2600;
  maxv = round(1e13);
var
  m,n,k: longint;
  c: array[1..maxk,1..maxk] of int64;
  a: array[1..maxn,1..maxn] of boolean;
  p: array[1..maxn] of longint;

  arg,matchX,matchY: array[1..maxk] of longint;
  Fx,Fy,d: array[1..maxk] of int64;

  queue,trace: array[1..maxk] of longint;
  front,rear: longint;

  start,fin: longint;
  res: int64;

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

  readln(fi, m);
  for i := 1 to m do read(fi, p[i]);
  readln(fi);

  fillchar(a, sizeof(a), false);
  for i := 1 to m do
    begin
      readln(fi, s);
      n := length(s);
      for j := 1 to n do
        if s[j] = 'Y' then a[i,j] := true;
    end;

  close(fi);

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

procedure network;
var
  i,j,t: longint;
  cost: int64;
begin
  k := 0;
  for i := 1 to maxk do
    for j := 1 to maxk do c[i,j] := maxv;

  for j := 1 to n do
    for i := 1 to m do if a[i,j] then
      for t := 1 to n do c[j,(t - 1) * m + i] := p[i] * (2 * t - 1);
  k := m * n;
end;

function get(i,j: longint): int64;
begin
  get := c[i,j] - Fx[i] - Fy[j];
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: longint;
  w: int64;
begin
  while front <= rear do
    begin
      i := queue[front];  inc(front);
      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;
                inc(rear);  queue[rear] := matchY[j];
              end;

            if d[j] > w then
              begin
                d[j] := w;
                arg[j] := i;
              end;
          end;
    end;
end;

procedure SubX_AddY;
var
  delta: int64;
  i,j: longint;
begin
  delta := maxv;
  for j := 1 to k do
    if (trace[j] = 0) and (delta > d[j]) 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;

        inc(rear);  queue[rear] := 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 n do
    begin
      start := i;
      initBFS;

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

      Enlarge;
    end;
end;

procedure printresult;
var
  f: text;
  i,j: longint;
begin
  assign(f, output);
    rewrite(f);

  res := 0;
  for i := 1 to n do
    begin
      j := matchX[i];
      if (j = 0) or (c[i,j] = maxv) then
        begin
          writeln(f, -1);
          close(f);
          exit;
        end;

      res := res + c[i,j];
    end;

  writeln(f, res);
  close(f);
end;

begin
  init;
  network;
  solve;
  printresult;
end.

Code mẫu của khuc_tuan

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>

using namespace std;

#define Rep(i,n) for(int i=0,lll=(n);i<lll;++i)
#define For(i,a,b) for(int i=(a),lll=(b);i<=lll;++i)
#define Ford(i,a,b) for(int i=(a),lll=(b);i>=lll;--i)
#define PB push_back
#define MP make_pair
#define SS(a) ((int)((a).size()))
#define VI vector<int>

class JobPlanner {
public:
    int minimalCost(vector <string>, vector <int>);
};

void tangluong(vector<VI> &f, int dt,int N,VI &la) {
    int v = N-1;
    while(v!=0) {
        int u = la[v];
        if(u<0) {
            u = -u-1;
            f[v][u] -= dt;
            v=u;
        }
        else {
            f[u][v] += dt;
            v=u;
        }
    }
}

bool bfs(vector<VI> &a, vector<VI> &f,int N) {
    queue<int> q;
    q.push(0);
    VI la(N), e(N);
    e[0] = 1000000;
    la[0]=0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int v=0;v<N;++v) if(e[v]==0) {
            if(f[u][v]<a[u][v]) {
                e[v] = min(e[u], a[u][v]-f[u][v]);
                la[v] = u;
                q.push(v);
            }
            else if(f[v][u]>0) {
                e[v] = min(e[u], f[v][u]);
                la[v] = -u-1;
                q.push(v);
            }
        }
        if(e[N-1]!=0) {
            tangluong(f, e[N-1], N, la);
            return true;
        }
    }
    return false;
}

int getflow(vector<VI> &a, vector<VI> &f) {
    int N=a.size();
    Rep(i, N) Rep(j, N) f[i][j] = 0;
    while(bfs(a,f,N)) ; 
}

int JobPlanner::minimalCost(vector <string> can, vector <int> cost) {
    int m = can.size();
    int n = can[0].length();
    vector<VI> a(m+n+2);
    for(int i=0;i<m+n+2;++i) a[i].resize(m+2+n);
    for(int i=1;i<=m;++i) a[0][i] = 100000;
    for(int i=1;i<=m;++i) for(int j=m+1;j<=m+n;++j) if(can[i-1][j-m-1]=='Y') a[i][j] = 1;
    for(int j=m+1;j<=m+n;++j) a[j][m+n+1] = 1;
    vector<VI> f(m+n+2);
    for(int i=0;i<m+n+2;++i) f[i].resize(m+2+n);
    getflow(a, f);
    //cout<<"Luong ok\n";
    for(int j=m+1;j<=m+n;++j) if(f[j][m+n+1]==0) return -1;
    int result = 0;
    for(int i=0;i<m;++i) {
        result += cost[i] * f[0][i+1] * f[0][i+1];
        a[0][i+1] = f[0][i+1];
    }
    bool ok = true;
    while(ok) {
        //cout<<result<<endl;
        ok = false;
        for(int i=1;i<=m;++i) if(a[0][i]>0) {
            for(int j=1;j<=m;++j) if(i!=j) {
                --a[0][i];
                ++a[0][j];
                int tmp = 0;
                for(int k=0;k<m;++k) tmp += cost[k] * a[0][k+1] * a[0][k+1];
                if(tmp<result) {
                    getflow(a, f);
                    bool test = true;
                    for(int k=m+1;k<=m+n;++k) if(f[k][m+n+1]==0) test = false;
                    if(test) {
                        result = tmp;
                        ok = true;
                        goto ttt;
                    }
                }
                ++a[0][i];
                --a[0][j];
            }
        }
        ttt : ;
    }
    return result;
}


int main() {
    int N;
    vector<string> vs;
    vector<int> vi;
    cin>>N;
    vi.resize(N);
    Rep(i,N) cin>>vi[i];
    vs.resize(N);
    getline(cin,vs[0]);
    Rep(i,N) getline(cin, vs[i]);
    cout<< (new JobPlanner())->minimalCost(vs, vi) <<endl;
    return 0;
}