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>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int oo = 1000111222;

vector <int> path;

struct edge
{
    int x, y, cap, flow, cost;
};

struct MinCostMaxFlow
{
    int n, S, T;
    vector < vector <int> > a;
    vector <int> dist, prev, done, pot;
    vector <edge> e;

    MinCostMaxFlow() {}
    MinCostMaxFlow(int _n, int _S, int _T)
    {
        n = _n; S = _S; T = _T;
        a = vector < vector <int> >(n + 1);
        dist = vector <int>(n + 1);
        prev = vector <int>(n + 1);
        done = vector <int>(n + 1);
        pot = vector <int>(n + 1, 0);
    }

    void addEdge(int x, int y, int _cap, int _cost)
    {
        edge e1 = {x, y, _cap, 0, _cost};
        edge e2 = {y, x, 0, 0, -_cost};
        a[x].push_back(e.size()); e.push_back(e1);
        a[y].push_back(e.size()); e.push_back(e2);
    }

    pair <int,int> dijkstra()
    {
        int flow = 0, cost = 0;
        for (int i = 1; i <= n; i++) done[i] = 0, dist[i] = oo;
        priority_queue < pair<int,int> > q;
        dist[S] = 0; prev[S] = -1;
        q.push(make_pair(0, S));
        while (!q.empty())
        {
            int x = q.top().second; q.pop();
            if (done[x]) continue;
            done[x] = 1;
            for (int i = 0; i < int(a[x].size()); i++)
            {
                int id = a[x][i], y = e[id].y;
                if (e[id].flow < e[id].cap)
                {
                    int D = dist[x] + e[id].cost + pot[x] - pot[y];
                    if (!done[y] && D < dist[y])
                    {
                        dist[y] = D; prev[y] = id;
                        q.push(make_pair(-dist[y], y));
                    }
                }
            }
        }

        for (int i = 1; i <= n; i++) pot[i] += dist[i];

        if (done[T])
        {
            flow = oo;
            for (int id = prev[T]; id >= 0; id = prev[e[id].x]) 
                flow = min(flow, e[id].cap - e[id].flow);
            for (int id = prev[T]; id >= 0; id = prev[e[id].x]) 
            {
                cost += e[id].cost * flow;
                e[id].flow += flow;
                e[id ^ 1].flow -= flow;
            }
        }

        return make_pair(flow, cost);
    }

    pair <int,int> minCostMaxFlow()
    {
        int totalFlow = 0, totalCost = 0;
        while (1)
        {
            pair <int,int> u = dijkstra();
            if (!done[T]) break;
            totalFlow += u.first; totalCost += u.second;
        }
        return make_pair(totalFlow, totalCost);
    }

    void trace(int x)
    {
        if (x == T)
        {
            cout << path.size();
            for (int i = 0; i < int(path.size()); i++) cout << ' ' << path[i];
            puts("");
            return;
        }
        path.push_back(x);
        for (int i = 0; i < int(a[x].size()); i++)
        {
            int id = a[x][i];
            if (e[id].flow > 0) 
            {
                if (e[id].y < T) e[id].flow = 0;
                trace(e[id].y);
                return;
            }
        }
    }
};

int main()
{
    int n, m, F, s, t, x, y, z;
    cin >> n >> m >> F >> s >> t;
    int S = n + 1, T = n + 2;
    MinCostMaxFlow u(T, S, T);
    while (m--) cin >> x >> y >> z, u.addEdge(x, y, 1, z), u.addEdge(y, x, 1, z);
    u.addEdge(S, s, F, 0);
    u.addEdge(t, T, F, 0);
    pair <int,int> ans = u.minCostMaxFlow();
    if (ans.first < F) puts("-1");
    else 
    {
        cout << ans.second << endl;
        while (F--) path.clear(), u.trace(s);
    }
}

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 N = 100, INF = 1e9;
vector<pair<int, int> > g[N+2];
vector<int> c, cost, f;
int n, m, k, s, t;

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

pair<int, int> mincost(int s, int t, int n) {
    int totalcost = 0, maxf = 0;
    while(true) {
        vector<int> d (n, INF);
        vector<pair<int, int> > tr (n, make_pair(INF, INF));
        vector<bool> inq (n, false);
        queue<int> q;
        d[s] = 0; q.push(s); inq[s] = true; tr[s] = make_pair(-1, -1);
        while(!q.empty()) {
            int u = q.front(); q.pop(); inq[u] = false;
            TR(g[u], it) {
                int v = it->first, e = it->second;
                if(c[e] > f[e] && d[v] > d[u] + cost[e]) {
                    d[v] = d[u] + cost[e];
                    tr[v] = make_pair(u, e);
                    if(!inq[v]) q.push(v), inq[v] = true;
                }
            }
        }
        if(d[t] == INF) break;
        int delta = INF;
        for(int u = tr[t].first, v = t; u != -1; v = u, u = tr[u].first)
            delta = min(delta, c[tr[v].second] - f[tr[v].second]);
        for(int u = tr[t].first, v = t; u != -1; v = u, u = tr[u].first) {
            f[tr[v].second] += delta;
            f[tr[v].second ^ 1] -= delta;
        }
        maxf += delta; totalcost += d[t] * delta;
    }
    return make_pair(maxf, totalcost);
}

void dfs(int s, int t, vector<int> &v, vector<bool> &used) {
    v.push_back(s);
    if(s == t) {
        cout << v.size();
        TR(v, i) cout << ' ' << *i+1;
        cout << '\n';
    } else {
        TR(g[s], it) {
            int u = it->first, e = it->second;
            if(!used[e] && c[e] == 1 && c[e] == f[e]) {
                used[e] = true;
                dfs(u, t, v, used);
                break;
            }
        }
    }
    v.pop_back();
}

void printRemain() {
    for(int u = 0; u < n; ++u) {
        TR(g[u], it) {
            int v = it->first, e = it->second;
            if(c[e] == 1 && f[e] == 1)
                cerr << "Remain " << u+1 << ' ' << v+1 << endl;
        }
    }
}

void enter() {
    cin >> n >> m >> k >> s >> t; --s; --t;
    for(int i = 0; i < m; ++i) {
        int u, v, c; cin >> u >> v >> c; --u; --v;
        addEdge(u, v, c, 1);
        addEdge(v, u, c, 1);
    }
    addEdge(n, s, 0, k);
    addEdge(t, n+1, 0, k);
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    pair<int, int> res = mincost(n, n+1, n+2);
    if(res.first < k) cout << -1 << '\n';
    else {
        cout << res.second << '\n';
        vector<int> tmp;
        vector<bool> used (c.size(), false);
        for(int i = 0; i < k; ++i) dfs(s, t, tmp, used);
    }
    return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, a, b) for(int i = (a); i <=(b); ++i)
#define FORD(i, a, b) for(int i = (a); i > (b); --i)
#define REPD(i, a, b) for(int i = (a); i >=(b); --i)
#define TR(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define RESET(a, v) memset(a, (v), sizeof(a))
#define SZ(a) (int(a.size()))
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
#define VII vector<II>
#define endl '\n'

const int N = 111;
const int INF = INT_MAX;

using namespace std;

int T[N], d[N];
bool inQ[N], was[N][N];
int cap[N][N], cost[N][N], flow[N][N];
int n, m, source, sink, minCost, maxFlow;

bool findPath() {
  queue<int> Q;
  REP(i, 1, n) {
    T[i] = inQ[i] = 0; d[i] = INF;
  }
  Q.push(source); inQ[source] = 1; d[source] = 0;
  while (!Q.empty()) {
    int u = Q.front(); Q.pop(); inQ[u] = 0;
    REP(v, 1, n)
    if (flow[u][v] < cap[u][v]) {
      int uv = cost[u][v] * (flow[u][v] < 0 ? -1: 1);
      if (d[v] > d[u] + uv) {
        d[v] = d[u] + uv;
        T[v] = u;
        if (!inQ[v]) {
          inQ[v] = 1;
          Q.push(v);
        }
      }
    }
  }
  return d[sink] < INF;
}

void incFlow() {
  int delta = INF;
  for (int v = sink, u = T[v]; v != source; v = u, u = T[v])
    delta = min(delta, flow[u][v] < 0 ? -flow[u][v] : (cap[u][v] - flow[u][v]));
  for (int v = sink, u = T[v]; v != source; v = u, u = T[v])
    flow[u][v] += delta, flow[v][u] -= delta;
  maxFlow += delta;
  minCost += delta * d[sink];
}

VI path;

void go(int u) {
  path.PB(u);
  REP(v, 1, n)
  if (flow[u][v] > 0 && !was[u][v]) {
    was[u][v] = 1; go(v); break;
  }
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  #ifdef _LAD_
    freopen("KWAY.in", "r", stdin);
  #endif // _LAD_
  cin >> n >> m >> maxFlow >> source >> sink;
  int u, v;
  FOR(i, 0, m) {
    cin >> u >> v; cin >> cost[u][v];
    cost[v][u] = cost[u][v];
    cap[u][v] = cap[v][u] = 1;
  }
  ++n;
  cap[n][source] = maxFlow;
  int S = source; source = n;
  int kway = maxFlow; maxFlow = 0;
  while (findPath()) incFlow();
  if (maxFlow < kway) cout << -1 << endl;
  else {
    cout << minCost << endl;
    while (kway--) {
      path.clear();
      go(S);
      cout << SZ(path) << ' ';
      for (int it: path)
        cout << it << ' ';
      cout << endl;
    }
  }
  return 0;
}

Code mẫu của RR

{$R+,Q+}
PROGRAM KWAY;
CONST
  fi='';
  fo='';
  maxn=100;
  max=1000000001;
VAR
  n,s,t:integer;
  k:integer;
  c:array[1..maxn,1..maxn] of longint;
  d:array[1..maxn,1..maxn] of byte;
  pre:array[1..maxn] of shortint;
  min:array[1..maxn] of longint;
Procedure ReadInput;
Var
  f:text;
  m,i:integer;
  u,v:integer;
Begin
  Assign(f,fi); Reset(f);
  Readln(f,n,m,k,s,t);
  For u:=1 to n do
    For v:=1 to n do
      c[u,v]:=max;
  For u:=1 to n do c[u,u]:=0;
  For i:=1 to m do
    begin
      Readln(f,u,v,c[u,v]);
      c[v,u]:=c[u,v];
    end;
  Close(f);
End;
Function min2(a,b:longint):longint;
Begin
  If a<b then min2:=a else min2:=b;
End;
Procedure KhoiTri;
Var
  i:integer;
Begin
  For i:=1 to n do
    min[i]:=max;
  min[s]:=0;
  pre[s]:=s;
End;
Procedure FindPath;
Var
  count,u,v:integer;
  stop:boolean;
Begin
  count:=0;
  repeat
    stop:=true;
    count:=count+1;
    For u:=1 to n do
      For v:=1 to n do
        If (d[u,v]=0) and (min[u]+c[u,v]<min[v]) then
          begin
            min[v]:=min[u]+c[u,v];
            stop:=false;
            pre[v]:=u;
          end
        else If (d[v,u]=1) and (min[u]-c[u,v]<min[v]) then
          begin
            min[v]:=min[u]-c[u,v];
            stop:=false;
            pre[v]:=-u;
          end;
  until (count=n-1) or stop;
End;
Procedure TangLuong;
Var
  i,next:integer;
Begin
  i:=t;
  repeat
    next:=i;
    i:=pre[i];
    If i<0 then d[next,-i]:=0
    else d[i,next]:=1;
    i:=abs(i);
  until i=s;
End;
Procedure Solve;
Var
  count:integer;
  stop:boolean;
Begin
  count:=0;
  repeat
    stop:=true; inc(count);
    KhoiTri;
    FindPath;
    If min[t]<max then
      begin
        stop:=false;
        TangLuong;
      end;
  until (count=k) or stop;
  If stop then min[t]:=max;
End;
Procedure WriteOutput;
Var
  f:text;
  i,next,u,sl:integer;
  cost:longint;
  ds:array[1..maxn] of integer;
Begin
  Assign(f,fo); Rewrite(f);
  If min[t]=max then begin Writeln(f,-1); Close(f); exit; end;
  cost:=0;
  For i:=1 to n do
    For next:=1 to n do
      If d[i,next]=1 then
        cost:=cost+c[i,next];
  Writeln(f,cost);
  For i:=1 to k do
    begin
      u:=s; sl:=1; ds[sl]:=s;
      repeat
        inc(sl);
        For next:=1 to n do
        If d[u,next]=1 then
          begin
            d[u,next]:=0;
            ds[sl]:=next;
            break;
          end;
        u:=next;
      until u=t;
      Write(f,sl,' ');
      For u:=1 to sl do
        Write(f,ds[u],' ');
      Writeln(f);
    end;
  Close(f);
End;
BEGIN
  ReadInput;
  Solve;
  WriteOutput;
END.

Code mẫu của ll931110

program KWAY;
const
  input  = '';
  output = '';
  maxn = 102;
  maxt = 1000000;
var
  d,c,f: array[1..maxn,1..maxn] of longint;
  free: array[1..maxn,1..maxn] of boolean;

  trace,best: array[1..maxn] of longint;

  list: array[1..maxn] of longint;
  nl: longint;

  n,m,k,s,t: longint;
  count: longint;
  fi,fo: text;

  q: array[0..maxn] of longint;
  inqueue: array[1..maxn] of boolean;
  front,rear: longint;

procedure openfile;
begin
  assign(fi, input);  reset(fi);
  assign(fo, output);  rewrite(fo);
end;

procedure init;
var
  u,v,i: longint;
begin
  readln(fi, n, m, k, s, t);
  fillchar(c, sizeof(c), 0);
  fillchar(d, sizeof(d), 0);
  fillchar(f, sizeof(f), 0);

  for i := 1 to m do
    begin
      readln(fi, u, v, d[u,v]);
      d[v,u] := d[u,v];
      c[u,v] := 1;  c[v,u] := 1;
    end;
end;

function FindPath: boolean;
var
  u,v: longint;
  nt,tmp: longint;
begin
  fillchar(trace, sizeof(trace), 0);
  fillchar(inqueue, sizeof(inqueue), false);
  for v := 1 to n do best[v] := maxt;
  best[s] := 0;

  front := 1;  rear := 1;  q[1] := s;
  nt := 1;
  repeat
    u := q[front];
    dec(nt);
    inqueue[u] := false;
    front := (front + 1) mod maxn;

    for v := 1 to n do
      if c[u,v] > f[u,v] then
        begin
          if f[u,v] = 0 then tmp := d[u,v] else tmp := d[u,v] * f[u,v] div abs(f[u,v]);
          if best[v] > best[u] + tmp then
            begin
              trace[v] := u;
              best[v] := best[u] + tmp;

              if not inqueue[v] then
                begin
                  inqueue[v] := true;
                  inc(nt);
                  rear := (rear + 1) mod maxn;
                  q[rear] := v;
                end;
            end;
        end;
  until nt = 0;

  FindPath := best[t] < maxt;
end;

procedure IncFlow;
var
  u,v: longint;
begin
  v := t;
  inc(count);
  while v <> s do
    begin
      u := trace[v];
      inc(f[u,v]);
      dec(f[v,u]);
      v := u;
    end;
end;

procedure solve;
begin
  count := 0;
  repeat
    if not FindPath then break;
    IncFlow;
  until count = k;
end;

procedure track(u: longint);
var
  v: longint;
begin
  inc(nl);  list[nl] := u;
  if u = t then exit;

  for v := 1 to n do
    if free[u,v] and (f[u,v] = 1) then
      begin
        free[u,v] := false;
        track(v);
        break;
      end;
end;

procedure printresult;
var
  i,j: longint;
  cost: longint;
begin
  if count < k then writeln(fo, -1) else
    begin
      fillchar(free, sizeof(free), true);
      cost := 0;
      for i := 1 to n do
        for j := 1 to n do
          if f[i,j] = 1 then cost := cost + d[i,j];

      writeln(fo, cost);
      for i := 1 to k do
        begin
          nl := 0;
          track(s);
          write(fo, nl, ' ');
          for j := 1 to nl do write(fo, list[j], ' ');
          writeln(fo);
        end;
    end;
end;

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

begin
  openfile;
  init;
  solve;
  printresult;
  closefile;
end.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   111
#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++)
#define fi   first
#define se   second
using namespace std;
const int INF=(int)1e9+7;
typedef pair<int,int> ii;
void minimize(int &x,const int &y) {
    if (x>y) x=y;
}
class MaxFlowMinCost {
    public:
    struct edge {
        int from,to,capa,flow,cost;
        edge() {
            from=0;to=0;capa=0;flow=0;cost=0;
        }
        edge(int u,int v,int ca,int co) {
            from=u;to=v;capa=ca;flow=0;cost=co;
        }   
        int residual(void) const {
            return (capa-flow);
        }
    };
    vector<vector<int> > g;
    vector<edge> e;
    vector<int> d,tr;
    int n;
    MaxFlowMinCost() {
        n=0;
    }
    MaxFlowMinCost(int n) {
        this->n=n;
        g.assign(n+7,vector<int>());
        e.clear();
        d=vector<int>(n+7);
        tr=vector<int>(n+7);
    }
    void addedge(int u,int v,int ca,int co) {
        g[u].push_back(e.size());
        e.push_back(edge(u,v,ca,co));
        g[v].push_back(e.size());
        e.push_back(edge(v,u,0,-co));       
    }
    bool FordBellman(int s,int t) {
        FOR(i,1,n) {
            d[i]=INF;
            tr[i]=-1;
        }
        vector<bool> inq=vector<bool>(n+7,false);
        queue<int> q;
        while (!q.empty()) q.pop();
        q.push(s);inq[s]=true;d[s]=0;
        while (!q.empty()) {
            int u=q.front();q.pop();inq[u]=false;
            FORE(it,g[u]) if (e[*it].residual()>0) {
                int v=e[*it].to;
                if (d[v]>d[u]+e[*it].cost) {
                    d[v]=d[u]+e[*it].cost;
                    tr[v]=*it;
                    if (!inq[v]) {
                        q.push(v);
                        inq[v]=true;
                    }
                }
            }
        }
        return (d[t]<INF);
    }
    ii getflow(int s,int t) {
        int totflow=0;
        int totcost=0;
        while (FordBellman(s,t)) {
            int delta=INF;
            for (int u=t;u!=s;u=e[tr[u]].from) minimize(delta,e[tr[u]].residual());
            for (int u=t;u!=s;u=e[tr[u]].from) {
                e[tr[u]].flow+=delta;
                e[tr[u]^1].flow-=delta;
            }
            totflow+=delta;
            totcost+=delta*d[t];
        }
        return (ii(totflow,totcost));
    }
};
queue<int> q[MAX];
MaxFlowMinCost g;
int n,m,k,s,t;
void loadgraph(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    scanf("%d",&k);
    scanf("%d",&s);
    scanf("%d",&t);
    g=MaxFlowMinCost(n+1);
    REP(i,m) {
        int u,v,c;
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%d",&c);
        g.addedge(u,v,1,c);
        g.addedge(v,u,1,c);
    }
    g.addedge(n+1,s,k,0);
}
void process(void) {
    ii res=g.getflow(n+1,t);
    if (res.fi<k) {
        printf("-1");
        return;
    }
    printf("%d\n",res.se);
    REP(i,g.e.size()) if (i%2==0 && g.e[i].flow>0 && g.e[i].from<=n) q[g.e[i].from].push(g.e[i].to);
    REP(zz,k) {
        vector<int> tmp;
        tmp.clear();
        int u=s;
        do {
            tmp.push_back(u);
            assert(!q[u].empty());
            int v=q[u].front();q[u].pop();
            u=v;
        }
        while (u!=t);
        tmp.push_back(t);
        printf("%d",tmp.size());
        FORE(it,tmp) printf(" %d",*it);
        printf("\n");
    }
}
int main(void) {
#ifndef ONLINE_JUDGE
    freopen("tmp.txt","r",stdin);
    printf("START\n");
#endif
    loadgraph();
    process();
    return 0;
}