Min-Cost Max-Flow
O(F·V·E) worst caseMaximum flow of minimum total cost: repeatedly push along the cheapest augmenting path, found with SPFA since reverse edges carry negative costs. Handles the standard assignment/transport reductions; for pure assignment the Hungarian template is faster.
// use it on
AtCoder Library Practice E ↗
A grid pick problem that reduces to min-cost flow with row and column nodes. Build the network and call min_cost_flow.
// the code
struct MCMF {
struct Edge { int to; long long cap, cost; };
int n;
vector<Edge> edges;
vector<vector<int>> g;
MCMF(int n) : n(n), g(n) {}
void add_edge(int u, int v, long long cap, long long cost) {
g[u].push_back(edges.size()); edges.push_back({v, cap, cost});
g[v].push_back(edges.size()); edges.push_back({u, 0, -cost});
}
pair<long long, long long> min_cost_flow(int s, int t) { // {flow, cost}
const long long INF = LLONG_MAX / 4;
long long flow = 0, cost = 0;
while (true) {
vector<long long> dist(n, INF);
vector<int> pe(n, -1);
vector<bool> inq(n, false);
deque<int> q = {s}; // SPFA
dist[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop_front();
inq[u] = false;
for (int id : g[u]) {
auto& e = edges[id];
if (e.cap > 0 && dist[u] + e.cost < dist[e.to]) {
dist[e.to] = dist[u] + e.cost;
pe[e.to] = id;
if (!inq[e.to]) {
inq[e.to] = true;
q.push_back(e.to);
}
}
}
}
if (dist[t] >= INF) break;
long long push = INF;
for (int v = t; v != s; v = edges[pe[v] ^ 1].to)
push = min(push, edges[pe[v]].cap);
for (int v = t; v != s; v = edges[pe[v] ^ 1].to) {
edges[pe[v]].cap -= push;
edges[pe[v] ^ 1].cap += push;
}
flow += push;
cost += push * dist[t];
}
return {flow, cost};
}
};// more matchings & flows