SyntaxPilot
Courses/Competitive Programming/Lesson 60
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 60 of 90

Min-cost max-flow

queued

These are the notes for Competitive Programming episode 60. In a min-cost flow network every edge has a capacity and a cost per unit of flow; min-cost max-flow (MCMF) sends the maximum flow (or a required amount K) at the lowest total cost. Delivery Riders is the assignment problem: the greedy "each rider takes the quickest free order" prints 14 where 10 is best, and trying every permutation is Time Limit Exceeded at n = 100. As a network (S → rider → order → T, capacity 1, cost = minutes), the answer is the cheapest flow of size n. The reverse edge now carries cost −c, a refund; successive shortest paths with SPFA (negative edges are allowed) gives 10, while a reverse edge with cost +c prints 14. Dijkstra with potentials (reduced costs c + pot[v] − pot[u] ≥ 0) gives the same answers faster. Ship the Mangoes sends exactly K crates: without the limit the code ships 4 and prints 20 where 13 is right; too little room prints -1. A stress test against every permutation passes. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

A food delivery hub has n riders and n waiting orders, and knows how many minutes each rider needs for each order. The manager first gives the quickest pairs away, then finds that the last riders are stuck with terrible ones. A smarter manager re-assigns: taking order 1 back from rider 1 gives back its 2 minutes, and giving it to rider 2 costs 3. Every change is a chain of "take back, give to someone else", and the manager always applies the cheapest chain that seats one more rider.

Definitions

  • Every edge a → b has a capacity c and a cost w per unit; sending f units costs f · w.
  • The cost of a flow is the sum of f · w over all edges.
  • Min-cost max-flow: among all maximum flows, one of least cost. Min-cost flow of value K: the cheapest flow of exactly K (or report that K is impossible).
  • Residual graph with costs: forward edge with room c − f and cost w; reverse edge with room f and cost −w (cancelling refunds the cost).
  • Successive shortest paths: repeatedly augment along the cheapest s → t path in the residual graph.

Problem H1 · Delivery Riders

(Written for this course, in the style of a classic assignment problem.)

  • Input: n (n ≤ 100), then an n × n matrix t (t[i][j] ≤ 1000 = minutes for rider i to deliver order j).
  • Output: the least total minutes when every rider gets exactly one order.
3
2 3 8
3 9 7
6 5 4

The answer is 10: rider 1 → order 2 (3), rider 2 → order 1 (3), rider 3 → order 3 (4).

The obvious attempt: the quickest free order (WA)

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

int n;
ll t[100][100];                                 // t[i][j] = minutes for rider i to deliver order j

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> t[i][j];
    vector<bool> taken(n);
    ll total = 0;
    for (int i = 0; i < n; i++) {               // each rider: the quickest free order
        int best = -1;
        for (int j = 0; j < n; j++)
            if (!taken[j] && (best < 0 || t[i][j] < t[i][best])) best = j;
        taken[best] = true;
        total += t[i][best];
    }
    cout << total << "\n";
}
14

Rider 1 grabs order 1 (2), rider 2 is left with 9 or 7 and takes 7, rider 3 gets 5: 14.

The safe attempt: every permutation (TLE)

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

int n;
ll t[100][100];                                 // t[i][j] = minutes for rider i to deliver order j

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> t[i][j];
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    ll best = LLONG_MAX;
    do {                                     // rider i gets order p[i]
        ll total = 0;
        for (int i = 0; i < n; i++) total += t[i][p[i]];
        best = min(best, total);
    } while (next_permutation(p.begin(), p.end()));
    cout << best << "\n";
}
10

For n = 100 there are 100! ≈ 9.3 · 10^157 permutations:

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

int n;
ll t[100][100];                                 // t[i][j] = minutes for rider i to deliver order j

int main() {
    n = 100;                                // 100 riders, 100 orders
    mt19937 rng(60);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) t[i][j] = rng() % 1000 + 1;
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    ll best = LLONG_MAX;
    do {                                     // rider i gets order p[i]
        ll total = 0;
        for (int i = 0; i < n; i++) total += t[i][p[i]];
        best = min(best, total);
    } while (next_permutation(p.begin(), p.end()));
    cout << best << "\n";
}
Time Limit Exceeded

The network

  • Source S = 0, riders 1 … n, orders n + 1 … 2n, sink T = 2n + 1.
  • S → rider i: capacity 1, cost 0. Order j → T: capacity 1, cost 0. Rider i → order j: capacity 1, cost t[i][j].
  • A flow of value n pairs every rider with a different order, and its cost is the total minutes. The minimum-cost flow of value n is the answer.

Refunds and cheapest paths

The reverse of an edge with cost w has cost −w: pushing flow back cancels the assignment and refunds its minutes. Successive shortest paths: while there is a path with room, take the cheapest one (counting refunds), push as much as its narrowest edge allows, and add d · dist[T] to the cost.

On the sample:

Step Cheapest path Cost
1 S → rider 1 → order 1 → T 2
2 S → rider 3 → order 3 → T (or the re-assignment below, also 4) 4
3 S → rider 2 → order 1 → (refund) rider 1 → order 2 → T: 3 − 2 + 3 4
total 10

Why it is optimal. A flow of value k is cheapest exactly when its residual graph has no negative-cost cycle. Augmenting along a shortest path keeps that property, so after each step the flow is the cheapest of its value. The same fact means the residual graph never contains a negative cycle, so the shortest paths are well defined.

Which shortest-path algorithm? Reverse edges have negative costs, so plain Dijkstra may be wrong. SPFA (Bellman-Ford with a queue: a vertex is re-queued whenever its distance drops) handles negative edges, in O(V · E) worst case per path.

The bug: a refund that charges

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

int n;
ll t[100][100];                                 // t[i][j] = minutes for rider i to deliver order j

struct Edge { int to; ll cap, cost; };
vector<Edge> e;
vector<int> g[205];

void addEdge(int a, int b, ll cap, ll cost) {
    g[a].push_back(e.size());
    e.push_back({b, cap, cost});
    g[b].push_back(e.size());
    e.push_back({a, 0, cost});
}

ll dist[205];
int via[205];                                   // via[v] = edge used to reach v
bool inq[205];
bool cheapest(int s, int tt, int V) {            // SPFA: costs can be negative
    fill(dist, dist + V, LLONG_MAX);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        inq[v] = false;
        for (int id : g[v]) {
            auto [u, cap, cost] = e[id];
            if (cap > 0 && dist[v] + cost < dist[u]) {
                dist[u] = dist[v] + cost;
                via[u] = id;
                if (!inq[u]) inq[u] = true, q.push(u);
            }
        }
    }
    return dist[tt] != LLONG_MAX;
}

pair<ll, ll> mcmf(int s, int tt, int V, ll limit) {   // {flow, cost}
    ll flow = 0, cost = 0;
    while (flow < limit && cheapest(s, tt, V)) {
        ll d = limit - flow;
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) d = min(d, e[via[v]].cap);
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) {
            e[via[v]].cap -= d;
            e[via[v] ^ 1].cap += d;
        }
        flow += d;
        cost += d * dist[tt];
    }
    return {flow, cost};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> t[i][j];
    int S = 0, T = 2 * n + 1;                 // riders 1..n, orders n+1..2n
    for (int i = 0; i < n; i++) {
        addEdge(S, i + 1, 1, 0);
        addEdge(n + 1 + i, T, 1, 0);
        for (int j = 0; j < n; j++) addEdge(i + 1, n + 1 + j, 1, t[i][j]);
    }
    cout << mcmf(S, T, T + 1, LLONG_MAX).second << "\n";
}
14

With cost +c on the reverse edge, undoing an assignment costs extra, so the algorithm never re-assigns and ends with the greedy's 14. With −c:

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

int n;
ll t[100][100];                                 // t[i][j] = minutes for rider i to deliver order j

struct Edge { int to; ll cap, cost; };
vector<Edge> e;
vector<int> g[205];

void addEdge(int a, int b, ll cap, ll cost) {
    g[a].push_back(e.size());
    e.push_back({b, cap, cost});
    g[b].push_back(e.size());
    e.push_back({a, 0, -cost});      // undo = a refund
}

ll dist[205];
int via[205];                                   // via[v] = edge used to reach v
bool inq[205];
bool cheapest(int s, int tt, int V) {            // SPFA: costs can be negative
    fill(dist, dist + V, LLONG_MAX);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        inq[v] = false;
        for (int id : g[v]) {
            auto [u, cap, cost] = e[id];
            if (cap > 0 && dist[v] + cost < dist[u]) {
                dist[u] = dist[v] + cost;
                via[u] = id;
                if (!inq[u]) inq[u] = true, q.push(u);
            }
        }
    }
    return dist[tt] != LLONG_MAX;
}

pair<ll, ll> mcmf(int s, int tt, int V, ll limit) {   // {flow, cost}
    ll flow = 0, cost = 0;
    while (flow < limit && cheapest(s, tt, V)) {
        ll d = limit - flow;
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) d = min(d, e[via[v]].cap);
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) {
            e[via[v]].cap -= d;
            e[via[v] ^ 1].cap += d;
        }
        flow += d;
        cost += d * dist[tt];
    }
    return {flow, cost};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> t[i][j];
    int S = 0, T = 2 * n + 1;                 // riders 1..n, orders n+1..2n
    for (int i = 0; i < n; i++) {
        addEdge(S, i + 1, 1, 0);
        addEdge(n + 1 + i, T, 1, 0);
        for (int j = 0; j < n; j++) addEdge(i + 1, n + 1 + j, 1, t[i][j]);
    }
    cout << mcmf(S, T, T + 1, LLONG_MAX).second << "\n";
}
10

One rider and one order:

42

A hundred riders with random times (1 … 1000 minutes):

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

int n;
ll t[100][100];                                 // t[i][j] = minutes for rider i to deliver order j

struct Edge { int to; ll cap, cost; };
vector<Edge> e;
vector<int> g[205];

void addEdge(int a, int b, ll cap, ll cost) {
    g[a].push_back(e.size());
    e.push_back({b, cap, cost});
    g[b].push_back(e.size());
    e.push_back({a, 0, -cost});      // undo = a refund
}

ll dist[205];
int via[205];                                   // via[v] = edge used to reach v
bool inq[205];
bool cheapest(int s, int tt, int V) {            // SPFA: costs can be negative
    fill(dist, dist + V, LLONG_MAX);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        inq[v] = false;
        for (int id : g[v]) {
            auto [u, cap, cost] = e[id];
            if (cap > 0 && dist[v] + cost < dist[u]) {
                dist[u] = dist[v] + cost;
                via[u] = id;
                if (!inq[u]) inq[u] = true, q.push(u);
            }
        }
    }
    return dist[tt] != LLONG_MAX;
}

pair<ll, ll> mcmf(int s, int tt, int V, ll limit) {   // {flow, cost}
    ll flow = 0, cost = 0;
    while (flow < limit && cheapest(s, tt, V)) {
        ll d = limit - flow;
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) d = min(d, e[via[v]].cap);
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) {
            e[via[v]].cap -= d;
            e[via[v] ^ 1].cap += d;
        }
        flow += d;
        cost += d * dist[tt];
    }
    return {flow, cost};
}

int main() {
    n = 100;                                // 100 riders, 100 orders
    mt19937 rng(60);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) t[i][j] = rng() % 1000 + 1;
    int S = 0, T = 2 * n + 1;                 // riders 1..n, orders n+1..2n
    for (int i = 0; i < n; i++) {
        addEdge(S, i + 1, 1, 0);
        addEdge(n + 1 + i, T, 1, 0);
        for (int j = 0; j < n; j++) addEdge(i + 1, n + 1 + j, 1, t[i][j]);
    }
    cout << mcmf(S, T, T + 1, LLONG_MAX).second << "\n";
}
1724

Stress test against every permutation

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

int n;
ll t[100][100];                                 // t[i][j] = minutes for rider i to deliver order j

struct Edge { int to; ll cap, cost; };
vector<Edge> e;
vector<int> g[205];

void addEdge(int a, int b, ll cap, ll cost) {
    g[a].push_back(e.size());
    e.push_back({b, cap, cost});
    g[b].push_back(e.size());
    e.push_back({a, 0, -cost});      // undo = a refund
}

ll dist[205];
int via[205];                                   // via[v] = edge used to reach v
bool inq[205];
bool cheapest(int s, int tt, int V) {            // SPFA: costs can be negative
    fill(dist, dist + V, LLONG_MAX);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        inq[v] = false;
        for (int id : g[v]) {
            auto [u, cap, cost] = e[id];
            if (cap > 0 && dist[v] + cost < dist[u]) {
                dist[u] = dist[v] + cost;
                via[u] = id;
                if (!inq[u]) inq[u] = true, q.push(u);
            }
        }
    }
    return dist[tt] != LLONG_MAX;
}

pair<ll, ll> mcmf(int s, int tt, int V, ll limit) {   // {flow, cost}
    ll flow = 0, cost = 0;
    while (flow < limit && cheapest(s, tt, V)) {
        ll d = limit - flow;
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) d = min(d, e[via[v]].cap);
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) {
            e[via[v]].cap -= d;
            e[via[v] ^ 1].cap += d;
        }
        flow += d;
        cost += d * dist[tt];
    }
    return {flow, cost};
}

int main() {
    mt19937 rng(60);
    for (int tc = 1; tc <= 500; tc++) {
        n = rng() % 7 + 1;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) t[i][j] = rng() % 20;
        vector<int> p(n);
        iota(p.begin(), p.end(), 0);
        ll best = LLONG_MAX;
        do {
            ll total = 0;
            for (int i = 0; i < n; i++) total += t[i][p[i]];
            best = min(best, total);
        } while (next_permutation(p.begin(), p.end()));
        e.clear();
        for (int v = 0; v <= 2 * n + 1; v++) g[v].clear();
        int S = 0, T = 2 * n + 1;
        for (int i = 0; i < n; i++) {
            addEdge(S, i + 1, 1, 0);
            addEdge(n + 1 + i, T, 1, 0);
            for (int j = 0; j < n; j++) addEdge(i + 1, n + 1 + j, 1, t[i][j]);
        }
        if (mcmf(S, T, T + 1, LLONG_MAX).second != best) { cout << "mismatch on test " << tc; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Dijkstra with potentials

Give every vertex a potential pot[v] = its true cheapest distance from S in the previous round, and use the reduced cost w'(v → u) = w + pot[v] − pot[u].

  • Because pot are true shortest distances, pot[u] ≤ pot[v] + w for every residual edge with room: w' ≥ 0. New edges created by augmenting lie on a shortest path, where w' = 0, and their reverses also have w' = 0.
  • Along any path S → T, the reduced costs add up to the real cost + pot[S] − pot[T]: the same shift for every path, so the cheapest path is the same.
  • After each Dijkstra, pot[v] += dist[v] (for reached v), and the real price of the path is pot[T] − pot[S].
  • Initial potentials 0 work when every original cost is ≥ 0 (as here); otherwise run one Bellman-Ford first.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
ll t[100][100];                                 // t[i][j] = minutes for rider i to deliver order j

struct Edge { int to; ll cap, cost; };
vector<Edge> e;
vector<int> g[205];

void addEdge(int a, int b, ll cap, ll cost) {
    g[a].push_back(e.size());
    e.push_back({b, cap, cost});
    g[b].push_back(e.size());
    e.push_back({a, 0, -cost});
}

ll dist[205], pot[205];                          // pot[v] = real distance found last round
int via[205];
bool cheapest(int s, int tt, int V) {            // Dijkstra on reduced costs
    fill(dist, dist + V, LLONG_MAX);
    dist[s] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, v] = pq.top();
        pq.pop();
        if (d != dist[v]) continue;
        for (int id : g[v]) {
            auto [u, cap, cost] = e[id];
            ll nd = d + cost + pot[v] - pot[u];      // reduced cost, never negative
            if (cap > 0 && nd < dist[u]) {
                dist[u] = nd;
                via[u] = id;
                pq.push({nd, u});
            }
        }
    }
    if (dist[tt] == LLONG_MAX) return false;
    for (int v = 0; v < V; v++) if (dist[v] != LLONG_MAX) pot[v] += dist[v];
    return true;
}

pair<ll, ll> mcmf(int s, int tt, int V, ll limit) {
    ll flow = 0, cost = 0;
    while (flow < limit && cheapest(s, tt, V)) {
        ll d = limit - flow;
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) d = min(d, e[via[v]].cap);
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) {
            e[via[v]].cap -= d;
            e[via[v] ^ 1].cap += d;
        }
        flow += d;
        cost += d * (pot[tt] - pot[s]);          // the real price of this path
    }
    return {flow, cost};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> t[i][j];
    int S = 0, T = 2 * n + 1;                 // riders 1..n, orders n+1..2n
    for (int i = 0; i < n; i++) {
        addEdge(S, i + 1, 1, 0);
        addEdge(n + 1 + i, T, 1, 0);
        for (int j = 0; j < n; j++) addEdge(i + 1, n + 1 + j, 1, t[i][j]);
    }
    cout << mcmf(S, T, T + 1, LLONG_MAX).second << "\n";
}
10
1724

Each round is O(E log V) instead of O(V · E).

Problem H2 · Ship the Mangoes

(Written for this course.)

n towns, m one-way roads; road a → b carries at most cap crates per day at cost per crate. Ship exactly K crates from the farm (1) to the market (n) at the least cost, or print −1.

4 5 3
1 2 2 1
1 3 2 4
2 3 1 1
2 4 1 6
3 4 3 1
Crate Cheapest path left Price
1 1 → 2 → 3 → 4 3
2, 3 1 → 3 → 4 5 each
4 1 → 2 → 4 7
5 no room (the roads into 4 carry 1 + 3) —

Successive shortest paths have non-decreasing prices, so the first K units are the cheapest K: stop at K by pushing min(d, K − flow).

The bug: no limit

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

struct Edge { int to; ll cap, cost; };
vector<Edge> e;
vector<int> g[205];

void addEdge(int a, int b, ll cap, ll cost) {
    g[a].push_back(e.size());
    e.push_back({b, cap, cost});
    g[b].push_back(e.size());
    e.push_back({a, 0, -cost});      // undo = a refund
}

ll dist[205];
int via[205];                                   // via[v] = edge used to reach v
bool inq[205];
bool cheapest(int s, int tt, int V) {            // SPFA: costs can be negative
    fill(dist, dist + V, LLONG_MAX);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        inq[v] = false;
        for (int id : g[v]) {
            auto [u, cap, cost] = e[id];
            if (cap > 0 && dist[v] + cost < dist[u]) {
                dist[u] = dist[v] + cost;
                via[u] = id;
                if (!inq[u]) inq[u] = true, q.push(u);
            }
        }
    }
    return dist[tt] != LLONG_MAX;
}

pair<ll, ll> mcmf(int s, int tt, int V, ll limit) {   // {flow, cost}
    ll flow = 0, cost = 0;
    while (flow < limit && cheapest(s, tt, V)) {
        ll d = limit - flow;
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) d = min(d, e[via[v]].cap);
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) {
            e[via[v]].cap -= d;
            e[via[v] ^ 1].cap += d;
        }
        flow += d;
        cost += d * dist[tt];
    }
    return {flow, cost};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    ll K;
    cin >> n >> m >> K;
    for (int i = 0; i < m; i++) {
        int a, b;
        ll cap, cost;
        cin >> a >> b >> cap >> cost;
        addEdge(a, b, cap, cost);   // cost per crate
    }
    auto [flow, cost] = mcmf(1, n, n + 1, LLONG_MAX);
    if (flow < K) cout << -1 << "\n";        // not enough room on the roads
    else cout << cost << "\n";
}
20

It shipped all 4 crates (3 + 5 + 5 + 7 = 20). With the limit K:

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

struct Edge { int to; ll cap, cost; };
vector<Edge> e;
vector<int> g[205];

void addEdge(int a, int b, ll cap, ll cost) {
    g[a].push_back(e.size());
    e.push_back({b, cap, cost});
    g[b].push_back(e.size());
    e.push_back({a, 0, -cost});      // undo = a refund
}

ll dist[205];
int via[205];                                   // via[v] = edge used to reach v
bool inq[205];
bool cheapest(int s, int tt, int V) {            // SPFA: costs can be negative
    fill(dist, dist + V, LLONG_MAX);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        inq[v] = false;
        for (int id : g[v]) {
            auto [u, cap, cost] = e[id];
            if (cap > 0 && dist[v] + cost < dist[u]) {
                dist[u] = dist[v] + cost;
                via[u] = id;
                if (!inq[u]) inq[u] = true, q.push(u);
            }
        }
    }
    return dist[tt] != LLONG_MAX;
}

pair<ll, ll> mcmf(int s, int tt, int V, ll limit) {   // {flow, cost}
    ll flow = 0, cost = 0;
    while (flow < limit && cheapest(s, tt, V)) {
        ll d = limit - flow;
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) d = min(d, e[via[v]].cap);
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) {
            e[via[v]].cap -= d;
            e[via[v] ^ 1].cap += d;
        }
        flow += d;
        cost += d * dist[tt];
    }
    return {flow, cost};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    ll K;
    cin >> n >> m >> K;
    for (int i = 0; i < m; i++) {
        int a, b;
        ll cap, cost;
        cin >> a >> b >> cap >> cost;
        addEdge(a, b, cap, cost);   // cost per crate
    }
    auto [flow, cost] = mcmf(1, n, n + 1, K);
    if (flow < K) cout << -1 << "\n";        // not enough room on the roads
    else cout << cost << "\n";
}
13

K = 5 is impossible:

4 5 5
1 2 2 1
1 3 2 4
2 3 1 1
2 4 1 6
3 4 3 1
-1

Complexity vs the constraints

Method Time Verdict at n = 100
quickest free order O(n²) Wrong Answer
every permutation O(n! · n) TLE
MCMF with SPFA F augmentations × O(V · E) worst; F = n = 100, V ≈ 200, E ≈ 10^4 accepted
MCMF with Dijkstra + potentials F × O(E log V) accepted, scales further
Hungarian algorithm (homework 3) O(n³) the standard for dense assignment

For general networks F is the flow value; if capacities are large, each augmentation still pushes the whole bottleneck, so the number of paths is usually far smaller than F.

Common mistakes (and the real outputs)

Mistake What you see Why Fix
greedy quickest pair 14 (expected 10) early choices block later ones min-cost flow
every permutation Time Limit Exceeded n! min-cost flow
reverse edge with cost +c 14 (expected 10) undo charges instead of refunding reverse cost −c
plain Dijkstra on raw costs wrong costs negative reverse edges SPFA, or potentials
no limit for "exactly K" 20 (expected 13) extra, pricier units shipped push min(d, K − flow)
forgetting the impossible case a cost printed for too little flow flow < K print −1
int cost overflow on big inputs flow × cost long long
dist initialised to INT_MAX and then dist + cost overflow, nonsense paths INF + cost LLONG_MAX and skip unreached vertices

Mini project

Write a MinCostFlow struct with addEdge(a, b, cap, cost), run(s, t, limit) returning {flow, cost}, and a switch between SPFA and Dijkstra-with-potentials. Test both on the samples, on random graphs against each other, and on random assignment matrices against next_permutation for n ≤ 8. Then solve homework 1, 2 and 4 with it and compare homework 3 (Hungarian) with it on 100 × 100 random matrices.

Practice

These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17).

1. Maximum-profit assignment. Same input; t[i][j] is now the profit.

Solution

Maximising Σ t is minimising Σ (−t): use cost −t[i][j]. SPFA handles the negative costs (there are no negative cycles in the initial graph, which is a DAG). Sample: the H1 matrix as profits gives 8 + 9 + 6 = 23.

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

int n;
ll t[100][100];                                 // t[i][j] = minutes for rider i to deliver order j

struct Edge { int to; ll cap, cost; };
vector<Edge> e;
vector<int> g[205];

void addEdge(int a, int b, ll cap, ll cost) {
    g[a].push_back(e.size());
    e.push_back({b, cap, cost});
    g[b].push_back(e.size());
    e.push_back({a, 0, -cost});      // undo = a refund
}

ll dist[205];
int via[205];                                   // via[v] = edge used to reach v
bool inq[205];
bool cheapest(int s, int tt, int V) {            // SPFA: costs can be negative
    fill(dist, dist + V, LLONG_MAX);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        inq[v] = false;
        for (int id : g[v]) {
            auto [u, cap, cost] = e[id];
            if (cap > 0 && dist[v] + cost < dist[u]) {
                dist[u] = dist[v] + cost;
                via[u] = id;
                if (!inq[u]) inq[u] = true, q.push(u);
            }
        }
    }
    return dist[tt] != LLONG_MAX;
}

pair<ll, ll> mcmf(int s, int tt, int V, ll limit) {   // {flow, cost}
    ll flow = 0, cost = 0;
    while (flow < limit && cheapest(s, tt, V)) {
        ll d = limit - flow;
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) d = min(d, e[via[v]].cap);
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) {
            e[via[v]].cap -= d;
            e[via[v] ^ 1].cap += d;
        }
        flow += d;
        cost += d * dist[tt];
    }
    return {flow, cost};
}

int main() {
    // t[i][j] = profit of giving order j to rider i: maximise = minimise the negated profits
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> t[i][j];
    int S = 0, T = 2 * n + 1;
    for (int i = 0; i < n; i++) {
        addEdge(S, i + 1, 1, 0);
        addEdge(n + 1 + i, T, 1, 0);
        for (int j = 0; j < n; j++) addEdge(i + 1, n + 1 + j, 1, -t[i][j]);   // negative costs: SPFA copes
    }
    cout << -mcmf(S, T, T + 1, LLONG_MAX).second << "\n";
}
23

2. Each rider can carry up to two orders. r riders, o orders; every order must be delivered.

Solution

Change one capacity: S → rider is 2. Every order still has capacity 1 into T. If the flow is less than o, print −1.

2 4
1 2 9 9
5 6 3 4
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int r, o;
ll t[100][100];   // t[i][j] = minutes for rider i, order j

struct Edge { int to; ll cap, cost; };
vector<Edge> e;
vector<int> g[205];

void addEdge(int a, int b, ll cap, ll cost) {
    g[a].push_back(e.size());
    e.push_back({b, cap, cost});
    g[b].push_back(e.size());
    e.push_back({a, 0, -cost});      // undo = a refund
}

ll dist[205];
int via[205];                                   // via[v] = edge used to reach v
bool inq[205];
bool cheapest(int s, int tt, int V) {            // SPFA: costs can be negative
    fill(dist, dist + V, LLONG_MAX);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        inq[v] = false;
        for (int id : g[v]) {
            auto [u, cap, cost] = e[id];
            if (cap > 0 && dist[v] + cost < dist[u]) {
                dist[u] = dist[v] + cost;
                via[u] = id;
                if (!inq[u]) inq[u] = true, q.push(u);
            }
        }
    }
    return dist[tt] != LLONG_MAX;
}

pair<ll, ll> mcmf(int s, int tt, int V, ll limit) {   // {flow, cost}
    ll flow = 0, cost = 0;
    while (flow < limit && cheapest(s, tt, V)) {
        ll d = limit - flow;
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) d = min(d, e[via[v]].cap);
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) {
            e[via[v]].cap -= d;
            e[via[v] ^ 1].cap += d;
        }
        flow += d;
        cost += d * dist[tt];
    }
    return {flow, cost};
}

int main() {
    // r riders, o orders (o <= 2r); every order delivered, each rider takes at most 2
    cin >> r >> o;
    for (int i = 0; i < r; i++)
        for (int j = 0; j < o; j++) cin >> t[i][j];
    int S = 0, T = r + o + 1;
    for (int i = 0; i < r; i++) addEdge(S, i + 1, 2, 0);              // capacity 2: up to two orders
    for (int j = 0; j < o; j++) addEdge(r + 1 + j, T, 1, 0);
    for (int i = 0; i < r; i++)
        for (int j = 0; j < o; j++) addEdge(i + 1, r + 1 + j, 1, t[i][j]);
    auto [flow, cost] = mcmf(S, T, T + 1, LLONG_MAX);
    if (flow < o) cout << -1 << "\n";
    else cout << cost << "\n";
}
10

3. The Hungarian algorithm, O(n³).

Solution

The Hungarian algorithm keeps potentials u (rows) and v (columns) with a[i][j] − u[i] − v[j] ≥ 0, adds rows one at a time, and grows a tree of zero-reduced-cost ("tight") edges, raising the potentials by the smallest slack until a free column is reached; then it flips the augmenting path. It is min-cost flow with potentials, specialised to the dense bipartite case. (Checked against all permutations on 200 random matrices.)

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

int main() {
    // Hungarian algorithm (potentials u, v on rows and columns), O(n^3). 1-indexed.
    int n;
    cin >> n;
    vector<vector<ll>> a(n + 1, vector<ll>(n + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> a[i][j];
    const ll INF = LLONG_MAX / 4;
    vector<ll> u(n + 1), v(n + 1);
    vector<int> p(n + 1), way(n + 1);       // p[j] = row matched to column j
    for (int i = 1; i <= n; i++) {
        p[0] = i;
        int j0 = 0;
        vector<ll> minv(n + 1, INF);
        vector<bool> used(n + 1, false);
        do {                                 // grow a tree of tight edges until a free column is reached
            used[j0] = true;
            int i0 = p[j0], j1 = 0;
            ll delta = INF;
            for (int j = 1; j <= n; j++)
                if (!used[j]) {
                    ll cur = a[i0][j] - u[i0] - v[j];
                    if (cur < minv[j]) minv[j] = cur, way[j] = j0;
                    if (minv[j] < delta) delta = minv[j], j1 = j;
                }
            for (int j = 0; j <= n; j++)
                if (used[j]) u[p[j]] += delta, v[j] -= delta;
                else minv[j] -= delta;
            j0 = j1;
        } while (p[j0] != 0);
        do {                                 // flip the augmenting path
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0);
    }
    ll total = 0;
    for (int j = 1; j <= n; j++) total += a[p[j]][j];
    cout << total << "\n";
}
10

4. The most crates for at most a fixed budget. Input: n m B, then the roads as in H2.

Solution

Augment along cheapest paths as long as the budget lasts; on a path of price p, send min(bottleneck, (B − spent) / p) crates. Prices never decrease, so once nothing is affordable, stop. Sample: budget 12 buys crate 1 (3) and crate 2 (5); a third would cost 5 more.

4 5 12
1 2 2 1
1 3 2 4
2 3 1 1
2 4 1 6
3 4 3 1
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Edge { int to; ll cap, cost; };
vector<Edge> e;
vector<int> g[205];

void addEdge(int a, int b, ll cap, ll cost) {
    g[a].push_back(e.size());
    e.push_back({b, cap, cost});
    g[b].push_back(e.size());
    e.push_back({a, 0, -cost});
}
ll dist[205];
int via[205];
bool inq[205];
bool cheapest(int s, int tt, int V) {
    fill(dist, dist + V, LLONG_MAX);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        inq[v] = false;
        for (int id : g[v]) {
            auto [u, cap, cost] = e[id];
            if (cap > 0 && dist[v] + cost < dist[u]) {
                dist[u] = dist[v] + cost;
                via[u] = id;
                if (!inq[u]) inq[u] = true, q.push(u);
            }
        }
    }
    return dist[tt] != LLONG_MAX;
}

int main() {
    // the most crates from 1 to n with total cost <= budget
    int n, m;
    ll budget;
    cin >> n >> m >> budget;
    for (int i = 0; i < m; i++) {
        int a, b;
        ll cap, cost;
        cin >> a >> b >> cap >> cost;
        addEdge(a, b, cap, cost);
    }
    ll flow = 0, spent = 0;
    while (cheapest(1, n, n + 1)) {
        ll d = LLONG_MAX, price = dist[n];
        for (int v = n; v != 1; v = e[via[v] ^ 1].to) d = min(d, e[via[v]].cap);
        if (price > 0) d = min(d, (budget - spent) / price);   // what we can still afford on this path
        if (d == 0) break;                                      // later paths cost at least as much
        for (int v = n; v != 1; v = e[via[v] ^ 1].to) {
            e[via[v]].cap -= d;
            e[via[v] ^ 1].cap += d;
        }
        flow += d;
        spent += d * price;
    }
    cout << flow << " crates, cost " << spent << "\n";
}
2 crates, cost 8

Quick quiz

Two riders, two orders. The least total minutes?

rider 1:  1  4
rider 2:  2  9

A) 5 · B) 6 · C) 10 · D) 11

Answer

B. Rider 1 → order 2 (4) and rider 2 → order 1 (2): 6. The greedy grabs the 1 and pays 9 for rider 2: 10.

Interview questions

  1. What is the assignment problem and how do you solve it? Pair n workers with n jobs at least total cost: min-cost perfect matching, by min-cost flow or the Hungarian algorithm in O(n³).
  2. Why does the reverse edge have cost −c? Pushing flow back cancels earlier flow and should refund its cost.
  3. What is successive shortest paths? Repeatedly augment along a cheapest s–t path in the residual graph; each intermediate flow is the cheapest of its value.
  4. When is a flow of value k of minimum cost? When its residual graph has no negative-cost cycle.
  5. Why can't you just use Dijkstra? Reverse edges have negative costs; with potentials (reduced costs ≥ 0) Dijkstra becomes valid.
  6. How do you send exactly K units? Cap each augmentation at K − flow; if the flow stops below K, it is impossible.
  7. How do you maximise profit instead? Negate the costs (and use an algorithm that handles negative edges, or add a constant).

Glossary

Term Meaning Example
Cost per unit The price of sending one unit along an edge rider 1 → order 2: 3
Min-cost flow The cheapest flow of a given value K crates
Min-cost max-flow (MCMF) The cheapest among the maximum flows H1
Assignment problem Pair n with n at least total cost riders and orders
Perfect matching Every vertex paired n riders, n orders
Residual graph Edges with room; reverse edges with cost −w refunds
Refund The negative cost of cancelling flow −2 for order 1
Successive shortest paths Augment along the cheapest path again and again 2, 4, 4
Negative cycle A cycle with total cost < 0 absent in an optimal flow's residual graph
SPFA Bellman-Ford with a queue cheapest()
Bellman-Ford Shortest paths that allow negative edges O(V · E)
Dijkstra Shortest paths for non-negative edges with potentials
Potential pot[v] A number per vertex that shifts edge costs last round's distances
Reduced cost w + pot[v] − pot[u] ≥ 0
via[v] The edge used to reach v on the cheapest path path recovery
Bottleneck The smallest room on a path d
Limit K The exact amount to send mcmf(…, K)
Hungarian algorithm O(n³) assignment with row and column potentials homework 3
Factorial n! 1 · 2 · … · n 100! ≈ 9.3 · 10^157
Stress test Comparing a fast solution with a slow, surely-correct one on many random inputs all 500 tests passed
Time Limit Exceeded (TLE) Too slow every permutation
Wrong Answer (WA) A wrong output 14, 20
Lazy propagation Postponing range updates in a segment tree next episode

Summary

  • Every edge has a capacity and a cost per unit; MCMF wants the most flow at the least cost.
  • The assignment problem is MCMF on S → riders → orders → T (capacity 1, cost = minutes); greedy prints 14, the answer is 10.
  • Reverse edges cost −c (a refund); +c prints 14 again.
  • Successive shortest paths with SPFA (negative edges), or Dijkstra with potentials (reduced costs ≥ 0).
  • For exactly K, push min(d, K − flow); print −1 if the flow stops short (20 without the limit, 13 with it).

Solutions in C++, Java and Python

Problem H1 · Delivery Riders

C++

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

int n;
ll t[100][100];                                 // t[i][j] = minutes for rider i to deliver order j

struct Edge { int to; ll cap, cost; };
vector<Edge> e;
vector<int> g[205];

void addEdge(int a, int b, ll cap, ll cost) {
    g[a].push_back(e.size());
    e.push_back({b, cap, cost});
    g[b].push_back(e.size());
    e.push_back({a, 0, -cost});      // undo = a refund
}

ll dist[205];
int via[205];                                   // via[v] = edge used to reach v
bool inq[205];
bool cheapest(int s, int tt, int V) {            // SPFA: costs can be negative
    fill(dist, dist + V, LLONG_MAX);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        inq[v] = false;
        for (int id : g[v]) {
            auto [u, cap, cost] = e[id];
            if (cap > 0 && dist[v] + cost < dist[u]) {
                dist[u] = dist[v] + cost;
                via[u] = id;
                if (!inq[u]) inq[u] = true, q.push(u);
            }
        }
    }
    return dist[tt] != LLONG_MAX;
}

pair<ll, ll> mcmf(int s, int tt, int V, ll limit) {   // {flow, cost}
    ll flow = 0, cost = 0;
    while (flow < limit && cheapest(s, tt, V)) {
        ll d = limit - flow;
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) d = min(d, e[via[v]].cap);
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) {
            e[via[v]].cap -= d;
            e[via[v] ^ 1].cap += d;
        }
        flow += d;
        cost += d * dist[tt];
    }
    return {flow, cost};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> t[i][j];
    int S = 0, T = 2 * n + 1;                 // riders 1..n, orders n+1..2n
    for (int i = 0; i < n; i++) {
        addEdge(S, i + 1, 1, 0);
        addEdge(n + 1 + i, T, 1, 0);
        for (int j = 0; j < n; j++) addEdge(i + 1, n + 1 + j, 1, t[i][j]);
    }
    cout << mcmf(S, T, T + 1, LLONG_MAX).second << "\n";
}

Java

import java.util.*;

public class Main {
    static int[] to = new int[100000], head, nxt = new int[100000], via;
    static long[] cap = new long[100000], cost = new long[100000], dist;
    static boolean[] inq;
    static int cnt = 0;

    static void addEdge(int a, int b, long c, long w) {      // edge i and its reverse i ^ 1
        to[cnt] = b; cap[cnt] = c; cost[cnt] = w; nxt[cnt] = head[a]; head[a] = cnt++;
        to[cnt] = a; cap[cnt] = 0; cost[cnt] = -w; nxt[cnt] = head[b]; head[b] = cnt++;   // undo = a refund
    }
    static boolean cheapest(int s, int t, int V) {          // SPFA: costs can be negative
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[s] = 0;
        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.add(s);
        while (!q.isEmpty()) {
            int v = q.poll();
            inq[v] = false;
            for (int id = head[v]; id != -1; id = nxt[id])
                if (cap[id] > 0 && dist[v] + cost[id] < dist[to[id]]) {
                    dist[to[id]] = dist[v] + cost[id];
                    via[to[id]] = id;
                    if (!inq[to[id]]) { inq[to[id]] = true; q.add(to[id]); }
                }
        }
        return dist[t] != Long.MAX_VALUE;
    }
    static long[] mcmf(int s, int t, int V, long limit) {   // {flow, cost}
        long flow = 0, total = 0;
        while (flow < limit && cheapest(s, t, V)) {
            long d = limit - flow;
            for (int v = t; v != s; v = to[via[v] ^ 1]) d = Math.min(d, cap[via[v]]);
            for (int v = t; v != s; v = to[via[v] ^ 1]) { cap[via[v]] -= d; cap[via[v] ^ 1] += d; }
            flow += d;
            total += d * dist[t];
        }
        return new long[]{flow, total};
    }
    static void init(int V) {
        head = new int[V]; Arrays.fill(head, -1);
        via = new int[V]; dist = new long[V]; inq = new boolean[V];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int S = 0, T = 2 * n + 1;                           // riders 1..n, orders n+1..2n
        init(T + 1);
        for (int i = 0; i < n; i++) { addEdge(S, i + 1, 1, 0); addEdge(n + 1 + i, T, 1, 0); }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) addEdge(i + 1, n + 1 + j, 1, sc.nextLong());
        System.out.println(mcmf(S, T, T + 1, Long.MAX_VALUE)[1]);
    }
}
10

Python

import sys
from collections import deque

class MinCostFlow:
    def __init__(self, V):
        self.V, self.g, self.to, self.cap, self.cost = V, [[] for _ in range(V)], [], [], []

    def add_edge(self, a, b, cap, cost):          # edge i and its reverse i ^ 1
        self.g[a].append(len(self.to)); self.to.append(b); self.cap.append(cap); self.cost.append(cost)
        self.g[b].append(len(self.to)); self.to.append(a); self.cap.append(0); self.cost.append(-cost)

    def run(self, s, t, limit=float("inf")):      # successive cheapest paths with SPFA
        flow = total = 0
        while flow < limit:
            dist, via, inq = [float("inf")] * self.V, [-1] * self.V, [False] * self.V
            dist[s] = 0
            q = deque([s])
            while q:
                v = q.popleft(); inq[v] = False
                for i in self.g[v]:
                    u = self.to[i]
                    if self.cap[i] > 0 and dist[v] + self.cost[i] < dist[u]:
                        dist[u] = dist[v] + self.cost[i]; via[u] = i
                        if not inq[u]:
                            inq[u] = True; q.append(u)
            if dist[t] == float("inf"):
                break
            d, v = limit - flow, t
            while v != s:
                d = min(d, self.cap[via[v]]); v = self.to[via[v] ^ 1]
            v = t
            while v != s:
                self.cap[via[v]] -= d; self.cap[via[v] ^ 1] += d; v = self.to[via[v] ^ 1]
            flow += d; total += d * dist[t]
        return flow, total

data = list(map(int, sys.stdin.read().split()))
n = data[0]
S, T = 0, 2 * n + 1                               # riders 1..n, orders n+1..2n
f = MinCostFlow(T + 1)
for i in range(n):
    f.add_edge(S, i + 1, 1, 0)
    f.add_edge(n + 1 + i, T, 1, 0)
    for j in range(n):
        f.add_edge(i + 1, n + 1 + j, 1, data[1 + i * n + j])
print(f.run(S, T)[1])
10

Problem H2 · Ship the Mangoes

C++

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

struct Edge { int to; ll cap, cost; };
vector<Edge> e;
vector<int> g[205];

void addEdge(int a, int b, ll cap, ll cost) {
    g[a].push_back(e.size());
    e.push_back({b, cap, cost});
    g[b].push_back(e.size());
    e.push_back({a, 0, -cost});      // undo = a refund
}

ll dist[205];
int via[205];                                   // via[v] = edge used to reach v
bool inq[205];
bool cheapest(int s, int tt, int V) {            // SPFA: costs can be negative
    fill(dist, dist + V, LLONG_MAX);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        inq[v] = false;
        for (int id : g[v]) {
            auto [u, cap, cost] = e[id];
            if (cap > 0 && dist[v] + cost < dist[u]) {
                dist[u] = dist[v] + cost;
                via[u] = id;
                if (!inq[u]) inq[u] = true, q.push(u);
            }
        }
    }
    return dist[tt] != LLONG_MAX;
}

pair<ll, ll> mcmf(int s, int tt, int V, ll limit) {   // {flow, cost}
    ll flow = 0, cost = 0;
    while (flow < limit && cheapest(s, tt, V)) {
        ll d = limit - flow;
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) d = min(d, e[via[v]].cap);
        for (int v = tt; v != s; v = e[via[v] ^ 1].to) {
            e[via[v]].cap -= d;
            e[via[v] ^ 1].cap += d;
        }
        flow += d;
        cost += d * dist[tt];
    }
    return {flow, cost};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    ll K;
    cin >> n >> m >> K;
    for (int i = 0; i < m; i++) {
        int a, b;
        ll cap, cost;
        cin >> a >> b >> cap >> cost;
        addEdge(a, b, cap, cost);   // cost per crate
    }
    auto [flow, cost] = mcmf(1, n, n + 1, K);
    if (flow < K) cout << -1 << "\n";        // not enough room on the roads
    else cout << cost << "\n";
}

Java

import java.util.*;

public class Main {
    static int[] to = new int[100000], head, nxt = new int[100000], via;
    static long[] cap = new long[100000], cost = new long[100000], dist;
    static boolean[] inq;
    static int cnt = 0;

    static void addEdge(int a, int b, long c, long w) {      // edge i and its reverse i ^ 1
        to[cnt] = b; cap[cnt] = c; cost[cnt] = w; nxt[cnt] = head[a]; head[a] = cnt++;
        to[cnt] = a; cap[cnt] = 0; cost[cnt] = -w; nxt[cnt] = head[b]; head[b] = cnt++;   // undo = a refund
    }
    static boolean cheapest(int s, int t, int V) {          // SPFA: costs can be negative
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[s] = 0;
        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.add(s);
        while (!q.isEmpty()) {
            int v = q.poll();
            inq[v] = false;
            for (int id = head[v]; id != -1; id = nxt[id])
                if (cap[id] > 0 && dist[v] + cost[id] < dist[to[id]]) {
                    dist[to[id]] = dist[v] + cost[id];
                    via[to[id]] = id;
                    if (!inq[to[id]]) { inq[to[id]] = true; q.add(to[id]); }
                }
        }
        return dist[t] != Long.MAX_VALUE;
    }
    static long[] mcmf(int s, int t, int V, long limit) {   // {flow, cost}
        long flow = 0, total = 0;
        while (flow < limit && cheapest(s, t, V)) {
            long d = limit - flow;
            for (int v = t; v != s; v = to[via[v] ^ 1]) d = Math.min(d, cap[via[v]]);
            for (int v = t; v != s; v = to[via[v] ^ 1]) { cap[via[v]] -= d; cap[via[v] ^ 1] += d; }
            flow += d;
            total += d * dist[t];
        }
        return new long[]{flow, total};
    }
    static void init(int V) {
        head = new int[V]; Arrays.fill(head, -1);
        via = new int[V]; dist = new long[V]; inq = new boolean[V];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        long K = sc.nextLong();
        init(n + 1);
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            long c = sc.nextLong(), w = sc.nextLong();
            addEdge(a, b, c, w);                           // cost per crate
        }
        long[] r = mcmf(1, n, n + 1, K);
        System.out.println(r[0] < K ? -1 : r[1]);
    }
}
13

Python

import sys
from collections import deque

class MinCostFlow:
    def __init__(self, V):
        self.V, self.g, self.to, self.cap, self.cost = V, [[] for _ in range(V)], [], [], []

    def add_edge(self, a, b, cap, cost):          # edge i and its reverse i ^ 1
        self.g[a].append(len(self.to)); self.to.append(b); self.cap.append(cap); self.cost.append(cost)
        self.g[b].append(len(self.to)); self.to.append(a); self.cap.append(0); self.cost.append(-cost)

    def run(self, s, t, limit=float("inf")):      # successive cheapest paths with SPFA
        flow = total = 0
        while flow < limit:
            dist, via, inq = [float("inf")] * self.V, [-1] * self.V, [False] * self.V
            dist[s] = 0
            q = deque([s])
            while q:
                v = q.popleft(); inq[v] = False
                for i in self.g[v]:
                    u = self.to[i]
                    if self.cap[i] > 0 and dist[v] + self.cost[i] < dist[u]:
                        dist[u] = dist[v] + self.cost[i]; via[u] = i
                        if not inq[u]:
                            inq[u] = True; q.append(u)
            if dist[t] == float("inf"):
                break
            d, v = limit - flow, t
            while v != s:
                d = min(d, self.cap[via[v]]); v = self.to[via[v] ^ 1]
            v = t
            while v != s:
                self.cap[via[v]] -= d; self.cap[via[v] ^ 1] += d; v = self.to[via[v] ^ 1]
            flow += d; total += d * dist[t]
        return flow, total

data = list(map(int, sys.stdin.read().split()))
n, m, K = data[0], data[1], data[2]
f = MinCostFlow(n + 1)
for i in range(m):
    a, b, c, w = data[3 + 4 * i: 7 + 4 * i]
    f.add_edge(a, b, c, w)                        # cost per crate
flow, cost = f.run(1, n, K)
print(-1 if flow < K else cost)
13