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 oo 1000000000
using namespace std;
int m,n,s,t,c[222][222],f[222][222],q[222],d[222],p[222];

void push(int &nq,int x,int y,int vl,int val)
{
     nq++; q[nq]=y; d[y]=x; p[y]=min(vl,val);
}

int find()
{
    int nq=1,i=1,x,y;
    fr(x,1,n) d[x]=0; 
    q[1]=s; d[s]=s; p[s]=oo;
    while (i<=nq)
    {
          x=q[i++];
          fr(y,1,n)
            if (!d[y])
            {
               if (f[x][y]<c[x][y]) push(nq,x,y,p[x],c[x][y]-f[x][y]);
               else
                   if (f[y][x]) push(nq,-x,y,p[x],f[y][x]);
               if (d[t]) return 1;
            }
    }
    return 0;
}

void incflow()
{
     int x=t,y,val=p[t];
     while (x!=s)
     {
           y=x; x=d[x];
           if (x>0) f[x][y]+=val;
           else
           {
               x=-x;
               f[y][x]-=val;
           }
     }
}

int main()
{
    int k,i,x,y,re=0;
    cin >> m >> n >> k;
    s=n+m+1; t=s+1;
    fr(i,1,m)
    {
       cin >> x; c[s][i]=x;
    }
    fr(i,1,n)
    {
       cin >> x; c[m+i][t]=x;
    }
    while (k--)
    {
       scanf("%d%d",&x,&y);
       c[x][y+m]=oo;
    }
    n+=m+2;
    while (find()) incflow();
    fr(i,1,m) re+=f[s][i];
    cout << re << endl;       
    return 0;
}

Code mẫu của happyboy99x

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

#define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int INF = 1e9;
vector<vector<pair<int, int> > > g;
vector<int> flow, c;
vector<pair<int, int> > trace;
int m, n, p;

template<class T> int size(const T &a) { return a.size(); }

void addEdge(int u, int v, int lim) {
    g[u].push_back(make_pair(v, size(c)));
    g[v].push_back(make_pair(u, size(c)+1));
    c.push_back(lim); c.push_back(0);
    flow.push_back(0); flow.push_back(0);
}

void enter() {
    cin >> m >> n >> p;
    g.resize(m+n+2); trace.resize(m+n+2);
    for(int i = 0; i < m; ++i) {
        int c; cin >> c;
        addEdge(0, i+1, c);
    }
    for(int i = 0; i < n; ++i) {
        int c; cin >> c;
        addEdge(m+i+1, m+n+1, c);
    }
    for(int i = 0; i < p; ++i) {
        int x, y; cin >> x >> y; --x; --y;
        addEdge(x+1, m+y+1, INF);
    }
}

int maxflow(int s, int t) {
    int res = 0;
    while(true) {
        fill(trace.begin(), trace.end(), make_pair(INF, INF));
        trace[s] = make_pair(-1, -1);
        queue<int> q; q.push(s);
        while(!q.empty()) {
            int u = q.front(); q.pop();
            if(u == t) break;
            TR(g[u], it) {
                int v = it->first, e = it->second;
                if(trace[v].first == INF && c[e] - flow[e] > 0)
                    trace[v] = make_pair(u, e), q.push(v);
            }
        }
        if(trace[t].first == INF) break;
        int delta = INF;
        for(int v = t, u = trace[v].first; u != -1; v = u, u = trace[u].first)
            delta = min(delta, c[trace[v].second] - flow[trace[v].second]);
        for(int v = t, u = trace[v].first; u != -1; v = u, u = trace[u].first) {
            int e = trace[v].second;
            flow[e] += delta;
            flow[e ^ 1] -= delta;
        }
        res += delta;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    cout << maxflow(0, m+n+1) << '\n';
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 300;
const int oo = trunc(1e9);
using namespace std;
int c[N][N], f[N][N];
int Q[N], T[N], cx[N], cy[N];
int m, n, k, s = 0, t;
vector<int> a[N];

bool FindPath() {
    int l = 1, r = 1, i, u, v;
    Q[1] = s;
    for(i=1; i<=t; i++) T[i] = -1;
    while (l <= r) {
        u = Q[l++];
        for(i=0; i<a[u].size(); i++) {
            v = a[u][i];
            if (T[v] < 0 && c[u][v] > f[u][v]) {
                Q[++r] = v;
                T[v] = u;
                if (v == t) return true;
            }
        }
    }
    return false;
}

void IncFlow() {
    int v = t, delta = oo, u;
    while (v != s) {
        u = T[v];
        delta = min(delta, c[u][v] - f[u][v]);
        v = u;
    }
    v = t;
    while (v != s) {
        u = T[v];
        f[u][v] += delta;
        f[v][u] -= delta;
        v = u;
    }
}

int main()
{
    scanf("%d %d %d\n", &m, &n, &k);
    int i; t = m + n + 1;
    for(i=1; i<=m; i++)
        scanf("%d", &cx[i]);
    for(i=1; i<=n; i++)
        scanf("%d", &cy[i]);

    int x, y;
    for(i=1; i<=k; i++) {
        scanf("%d %d", &x, &y);
        c[x][m + y] = oo;
        a[x].push_back(m + y);
        a[m + y].push_back(x);
        if (c[s][x] == 0) {
            c[s][x] = cx[x];
            a[s].push_back(x);
        }
        if (c[m + y][t] == 0) {
            c[m + y][t] = cy[y];
            a[m + y].push_back(t);
        }
    }
    while (FindPath())
        IncFlow();
    int res = 0;
    for(i=1; i<=m; i++) res += f[s][i];
    printf("%d", res);
    return 0;
}

Code mẫu của RR

{$R+,Q+}
PROGRAM NKLIGHT;
CONST
  fi='';
  fo='';
  maxn=100;
  oo=101;
VAR
  m,n:longint;
  d,c:array[0..2*maxn+1,0..2*maxn+1] of integer;
  trace,dt,xet:array[0..2*maxn+1] of integer;
  s,t:longint;
  queue:array[1..2*maxn+2] of longint;
  first,last:longint;
Procedure ReadInput;
Var
  f:text;
  i,k:longint;
  u,v:longint;
Begin
  Assign(f,fi); Reset(f);
  Readln(f,m,n,k);
  s:=0; t:=m+n+1;
  For i:=1 to m do
    Read(f,c[s,i]);
  For i:=1 to n do
    Read(f,c[m+i,t]);
  For i:=1 to k do
  begin
    Readln(f,u,v);
    c[u,m+v]:=oo;
  end;
  Close(f);
End;
Procedure Init;
Var
  i:integer;
Begin
  Fillchar(xet,sizeof(xet),0);
  Fillchar(dt,sizeof(dt),0);
  For i:=1 to m+n+1 do trace[i]:=-1;
  trace[0]:=0;
  first:=1; last:=1;
  queue[1]:=s;
  xet[s]:=1;
  dt[s]:=oo;
End;
Function min(a,b:longint):longint;
Begin
  If a<b then min:=a else min:=b;
End;
Procedure FindPath;
Var
  i,u:longint;
Begin
  While first<=last do
  begin
    u:=queue[first]; inc(first);
    For i:=1 to m+n+1 do
    If (c[u,i]>0) and (d[u,i]<c[u,i]) and (xet[i]=0) then
      begin
        xet[i]:=1;
        dt[i]:=min(dt[u],c[u,i]-d[u,i]);
        trace[i]:=u;
        inc(last); queue[last]:=i;
      end
    else If (d[i,u]>0) and (xet[i]=0) and (c[i,u]>0) then
      begin
        xet[i]:=1;
        dt[i]:=min(dt[u],d[i,u]);
        trace[i]:=-u;
        inc(last); queue[last]:=i;
      end;
  end;
End;
Procedure IncFlow;
Var
  x,pre:longint;
Begin
  x:=t;
  repeat
    pre:=trace[x];
    If pre>=0 then d[pre,x]:=d[pre,x]+dt[t]
    else d[x,-pre]:=d[x,-pre]-dt[t];
    x:=abs(pre);
  until x=s;
End;
Procedure Solve;
Var
  i:integer;
Begin
  repeat
    Init;
    FindPath;
    If dt[t]>0 then IncFlow;
  until dt[t]=0;
End;
Procedure WriteOutput;
Var
  f:text;
  p,q,i,j:longint;
  cost:longint;
Begin
  Assign(f,fo); Rewrite(f);
  p:=0; q:=0;
  cost:=0;
  For i:=1 to m do
    If trace[i]=-1 then
      begin
        cost:=cost+c[0,i];
        inc(p);
      end;
  For i:=1 to n do
    If trace[m+i]<>-1 then
      begin
        cost:=cost+c[m+i,t];
        inc(q);
      end;
  Writeln(f,cost);
{  Writeln(f,p,' ',q);
  For i:=1 to m do
    If trace[i]=-1 then Writeln(f,i);
  For i:=1 to n do
    If trace[m+i]<>-1 then Writeln(f,i);}
  Close(f);
End;
BEGIN
  ReadInput;
  Solve;
  WriteOutput;
END.

Code mẫu của hieult

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
//#include <conio.h>
#define maxc 1111111111
#define maxn 311

using namespace std;

int n,m,k,s,t,c[maxn][maxn],f[maxn][maxn],qu[maxn],tr[maxn];

bool coduongtang(){
     int dau,cuoi,u,v;
     memset(tr,0,sizeof(tr));
     dau = 1; cuoi = 1;
     qu[dau] = s;
     tr[s] = n+m+3;
    // printf("co\n");
     do{
           u = qu[dau]; dau++;
           for(v = 1;v<=n+m+2;v++){
                if(tr[v]==0 && c[u][v]>f[u][v]){
                     tr[v] = u;
                     if(v==t)
                          return true;
                     cuoi++; qu[cuoi] = v;
                }
           }
     }while(dau<=cuoi);
     return false;
}

void duongtang(){
     int delta,u,v;
     delta = maxc;
     v = t;
     do{
         u = tr[v];
         if(c[u][v]-f[u][v]<delta) delta = c[u][v]-f[u][v];
         v = u;
     }while(v!=s);
     v = t;
     do{
         u = tr[v];
         f[u][v] = f[u][v]+delta;
         f[v][u] = f[v][u]-delta;
         v = u;
     }while(v!=s);
}

int main(){
     //freopen("LIGHT.in","r",stdin);
     int i,u,v;
     scanf("%d %d %d",&m,&n,&k);
     memset(c,0,sizeof(c));
     for(int i = 1;i<=m;i++) scanf("%d",&c[1][i+1]);
     for(int i = 1;i<=n;i++) scanf("%d",&c[m+i+1][n+m+2]);
     for(int i = 1;i<=k;i++){
          scanf("%d %d",&u,&v);
          c[u+1][m+v+1] = maxc;
     }
     s = 1;
     t = n+m+2;
     memset(f,0,sizeof(f));
     do{
          if(coduongtang()) duongtang();
          else break;
     }while(true);
     int w = 0;
     for(u = 1;u<=n+m+2;u++){
          if(f[s][u]>0)
              w+=f[s][u];
     }
     printf("%d",w);
     //getch();
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#define INF 1000000000
typedef long long ll;
using namespace std;

int f[210][210],c[210][210];
int trace[210];
int n,m,k;
int cnt = 0;
int start,end;
vector<int> adj[210];

bool findPath()
{
//     cout << "begin findpath" << endl;
     memset(trace,0,sizeof(trace));
     queue<int> q;  q.push(start);  trace[start] = -1;
     while (!q.empty())
     {
           int u = q.front();  q.pop();
           for (int i = 0; i < adj[u].size(); i++)
           {
               int v = adj[u][i];
               if (!trace[v] && c[u][v] > f[u][v])
               {
                  trace[v] = u;
                  if (v == end) return true;
                  q.push(v);
               };
           };
     };
     return false;
};

void IncFlow()
{
     int delta = INF,v = end;
     while (v != start)
     {
           int u = trace[v];
           delta = min(delta,c[u][v] - f[u][v]);
           v = u;
     };
     v = end;
     while (v != start)
     {
           int u = trace[v];
           f[u][v] += delta;  f[v][u] -= delta;
           v = u;
     };
};

void add_edge(int u,int v,int cost)
{
     adj[u].push_back(v);
     adj[v].push_back(u);
     c[u][v] = cost;
};

void maxFlow()
{
     while (1)
     {
           if (!findPath()) break;
           IncFlow();           
     };
};

int main()
{
//    freopen("light.in","r",stdin);
//    freopen("light.ou","w",stdout);
    scanf("%d %d %d", &m, &n, &k);
    start = 1;  end = n + m + 2;
    memset(c,0,sizeof(c));
    for (int i = 1; i <= m; i++)
    {
        int x;  scanf("%d", &x);
        add_edge(start,1 + i,x);
    };
    for (int i = 1; i <= n; i++)
    {
        int x;  scanf("%d", &x);
        add_edge(m + i + 1,end,x);
    };
    for (int i = 0; i < k; i++)
    {
        int x,y;
        scanf("%d %d", &x, &y);
        add_edge(1 + x,m + 1 + y,INF);
    };

/*    for (int i = 1; i <= end; i++)
    {
        for (int j = 0; j < adj[i].size(); j++) cout << adj[i][j] << ' ';
        cout << endl;        
    };*/

    memset(f,0,sizeof(f));
    maxFlow();
    int ret = 0;
    for (int i = 0; i < adj[start].size(); i++)
    {
        int v = adj[start][i];
        ret += f[start][v];
    };
    printf("%d\n", ret);
};

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
const int INF=(int)1e9+7;
class DinicFlow {
    private:
    vector<int> dist,head,q,work;
    vector<int> capa,flow,next,point;
    int n,m;
    public:
    DinicFlow() {
        n=0;m=0;
    }
    DinicFlow(int n,int _m) {
        this->n=n;
        this->m=0;
        dist=vector<int>(n+7);
        head=vector<int>(n+7,-1);
        q=vector<int>(n+7);
        work=vector<int>(n+7);
        int m=2*_m;
        capa=vector<int>(m+7);
        flow=vector<int>(m+7,0);
        next=vector<int>(m+7);
        point=vector<int>(m+7);     
    }
    void addedge(int u,int v,int c1,int c2) {
        point[m]=v;capa[m]=c1;flow[m]=0;next[m]=head[u];head[u]=m;m++;
        point[m]=u;capa[m]=c2;flow[m]=0;next[m]=head[v];head[v]=m;m++;
    }
    bool bfs(int s,int t) {
        FORE(it,dist) *it=-1;
        int sz=1;
        q[0]=s;dist[s]=0;
        REP(x,sz) {
            int u=q[x];
            for (int i=head[u];i>=0;i=next[i])
                if (dist[point[i]]<0 && flow[i]<capa[i]) {
                    dist[point[i]]=dist[u]+1;
                    q[sz]=point[i];
                    sz++;
                }
        }
        return (dist[t]>=0);
    }
    int dfs(int s,int t,int f) {
        if (s==t) return (f);
        for (int &i=work[s];i>=0;i=next[i])
            if (dist[point[i]]==dist[s]+1 && flow[i]<capa[i]) {
                int d=dfs(point[i],t,min(f,capa[i]-flow[i])) ;
                if (d>0) {
                    flow[i]+=d;
                    flow[i^1]-=d;
                    return (d);
                }
            }
        return (0);
    }
    int maxflow(int s,int t) {
        int ret=0;
        while (bfs(s,t)) {
            FOR(i,1,n) work[i]=head[i];
            while (true) {
                int d=dfs(s,t,INF);
                if (d<=0) break;
                ret+=d;
            }
        }
        return (ret);
    }
};
int m,n,k;
DinicFlow g;
void init(void) {
    scanf("%d",&m);
    scanf("%d",&n);
    scanf("%d",&k);
    g=DinicFlow(m+n+2,m+n+k);
    FOR(i,1,m) {
        int t;
        scanf("%d",&t);
        g.addedge(m+n+1,i,t,0);     
    }
    FOR(i,1,n) {
        int t;
        scanf("%d",&t);
        g.addedge(m+i,m+n+2,t,0);           
    }
    REP(i,k) {
        int x,y;
        scanf("%d",&x);
        scanf("%d",&y);
        g.addedge(x,m+y,INF,0);
    }
    printf("%d",g.maxflow(m+n+1,m+n+2));
}
int main(void) {
    init();
    return 0;
}

Code mẫu của khuc_tuan

import java.io.*;
import java.util.*;

public class Main {

    int n,m,k,st,en,sl;
    int[] a,b,q,la,e;
    int[][] c, f;

    void nhap() throws Exception{
        BufferedReader kb=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(kb.readLine());
        m=Integer.parseInt(st.nextToken());
        n=Integer.parseInt(st.nextToken());
        k=Integer.parseInt(st.nextToken());
        en=m+n+2;
        a=new int[m+1];
        b=new int[n+1];
        c=new int[m+n+3][m+n+3];
        f=new int[m+n+3][m+n+3];
        q=new int[m+n+3];
        la=new int[m+n+3];
        e=new int[m+n+3];
        st=new StringTokenizer(kb.readLine());
        for(int i=1;i<=m;++i) a[i]=Integer.parseInt(st.nextToken());
        st=new StringTokenizer(kb.readLine());
        for(int i=1;i<=n;++i) b[i]=Integer.parseInt(st.nextToken());
        int u,v;
        for(int i=1;i<=k;++i){
            st=new StringTokenizer(kb.readLine());
            u=Integer.parseInt(st.nextToken());
            v=Integer.parseInt(st.nextToken());
            c[u][v+m]=100000000;
        }
        for(int i=1;i<=m;++i) c[en-1][i]=a[i];
        for(int i=1;i<=n;++i) c[i+m][en]=b[i];
    }

    void tangluong(int v){
        int u,dt=e[v];
        sl+=dt;
        while(v!=st){
            u=la[v];
            if(u<0){
                u=-u;
                f[v][u]-=dt;
                v=u;
            }
            else{
                f[u][v]+=dt;
                v=u;
            }
        }
    }

    boolean bfs(){
        int l,r,u,v;
        q[l=r=0]=st;
        Arrays.fill(la,0);
        Arrays.fill(e,0);
        e[st]=100000000;
        la[st]=st;
        while(l<=r){
            u=q[l++];
            for(v=1;v<=en;++v) if(e[v]==0){
                if(c[u][v]>f[u][v]){
                    e[v]=Math.min(e[u],c[u][v]-f[u][v]);
                    la[v]=u;
                    q[++r]=v;
                }
                else if(f[v][u]>0) {
                    e[v]=Math.min(e[u],f[v][u]);
                    la[v]=-u;
                    q[++r]=v;
                }
            }
            if(e[en]>0) {
                tangluong(en);
                return true;
            }
        }
        return false;
    }

    void xuly(){
        st=en-1;
        while( bfs() ) ;
        System.out.println(sl);
    }

    void run() throws Exception{
        nhap();
        xuly();
    }

    public static void main(String[] args) throws Exception {
        new Main().run();
    }
}