模板分享：网络最小费用流

Code

改自 jiangly 的模板，使用 Primal-Dual 算法.

template<class Flow, class Cost>
struct MCFGraph {struct Edge {int v;Flow c;Cost f;Edge(int v, Flow c, Cost f) : v(v), c(c), f(f) {}};const int n;std::vector<Edge> e;std::vector<std::vector<int>> g;std::vector<Cost> h, dis;std::vector<int> pre;bool dijkstra(int s, int t) {dis.assign(n, std::numeric_limits<Cost>::max());pre.assign(n, -1);std::priority_queue<std::pair<Cost, int>, std::vector<std::pair<Cost, int>>, std::greater<std::pair<Cost, int>>> que;dis[s] = 0;que.emplace(0, s);while (!que.empty()) {Cost d = que.top().first;int u = que.top().second;que.pop();if (dis[u] < d) continue;for (int i : g[u]) {int v = e[i].v;Flow c = e[i].c;Cost f = e[i].f;if (c > 0 && dis[v] > d + h[u] - h[v] + f) {dis[v] = d + h[u] - h[v] + f;pre[v] = i;que.emplace(dis[v], v);}}}return dis[t] != std::numeric_limits<Cost>::max();}MCFGraph(int n) : n(n), g(n) {}void addEdge(int u, int v, Flow c, Cost f) {g[u].push_back(e.size());e.emplace_back(v, c, f);g[v].push_back(e.size());e.emplace_back(u, 0, -f);}std::pair<Flow, Cost> flow(int s, int t) {Flow flow = 0;Cost cost = 0;h.assign(n, 0);while (dijkstra(s, t)) {for (int i = 0; i < n; ++i) h[i] += dis[i];Flow aug = std::numeric_limits<Flow>::max();for (int i = t; i != s; i = e[pre[i] ^ 1].v) aug = std::min(aug, e[pre[i]].c);for (int i = t; i != s; i = e[pre[i] ^ 1].v) {e[pre[i]].c -= aug;e[pre[i] ^ 1].c += aug;}flow += aug;cost += h[t] * aug;}return std::make_pair(flow, cost);}
};

Usage

MCFGraph<Flow, Cost>::MCFGraph(int n);

创建一个网络图，有 $n$ 个点，没有弧，容量类型为 Flow，费用类型为 Cost（只支持整数）

void MCFGraph<Flow, Cost>::addEdge(int u, int v, Flow c, Cost f);

在图中加入一条 $u\to v$，流量为 $c$ ，单位流量费用为 $f$ 的有向弧.
$0\le u,v<n$，$c$ 不超过 Flow 的范围， $f$ 不超过 Cost 的范围.

pair<Flow, Cost> MCFGraph<Flow, Cost>::flow(int s, int t);

求出 $s$ 到 $t$ 的最小费用最大流（图会变为残量网络）
需要保证 first，second 在 Flow，Cost 范围内.
$0\le s,t<n$

注意：不支持一边跑 flow 一边加弧.