暴力
int vis[N], lst[N];
ll dis[N], flow[N];
int SPFA() {
rep(i, 1, n) dis[i] = INF;
queue<int> q;
q.push(s), dis[s] = 0, flow[s] = INF;
while (!q.empty()) {
int u = q.front();
q.pop(), vis[u] = 0;
for (int i = h[u]; i; i = e[i].n) {
int v = e[i].t;
if (e[i].w && dis[v] > dis[u] + e[i].c) {
dis[v] = dis[u] + e[i].c;
lst[v] = i, flow[v] = min(flow[u], e[i].w);
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return dis[t] < INF;
}
ll F = 0, C = 0;
while (SPFA()) {
ll ret = flow[t];
F += ret, C += ret * dis[t];
for (int u = t; u != s; u = e[lst[u] ^ 1].t)
e[lst[u]].w -= ret, e[lst[u] ^ 1].w += ret;
}
原始对偶算法
英文：Primal-Dual
用处：用 Dijkstra 跑费用流，不支持负环
用 Johnson 里面的技巧，给每个点定义 \(h_u\)，边 \((u,v,w)\) 的新边权为 \(w+h_u-h_v\)
为了让新边权 \(\ge0\)，以源点为起始点跑最短路后 \(h_u\gets d_u\) 即可。
每次增广后，令 \(h_u\gets h_u+d_u\) 即可。
int vis[N];
ll H[N];
void SPFA() {
memset(vis, 0, sizeof(vis));
memset(H, 0x3f, sizeof(H));
vis[s] = 1, H[s] = 0;
queue<int> q;
q.push(s), vis[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop(), vis[u] = 0;
for (int i = h[u]; i; i = e[i].n) {
int v = e[i].t;
if (e[i].w && H[v] > H[u] + e[i].c) {
H[v] = H[u] + e[i].c;
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
}
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
ll dis[N], flow[N];
int lst[N];
void Dijkstra() {
memset(vis, 0, sizeof(vis));
rep(i, 1, n) dis[i] = INF;
dis[s] = 0, flow[s] = INF;
q.push({0ll, s});
while (!q.empty()) {
int u = q.top().second;
ll d = q.top().first;
q.pop();
if (d > dis[u]) continue;
for (int i = h[u]; i; i = e[i].n) {
int v = e[i].t;
if (e[i].w && dis[v] > dis[u] + e[i].c) {
dis[v] = dis[u] + e[i].c;
lst[v] = i;
flow[v] = min(flow[u], e[i].w);
q.push({dis[v], v});
}
}
}
}
ll F = 0, C = 0;
SPFA();
while (1) {
Dijkstra();
if (dis[t] == INF) break;
ll ret = flow[t];
F += ret, C += ret * dis[t];
for (int u = t; u != s; u = e[lst[u] ^ 1].t)
e[lst[u]].w -= ret, e[lst[u] ^ 1].w += ret;
rep(i, 1, n) H[i] += dis[i];
}
cout << F << '\n' << C << '\n';
单纯形网络流
英文：Simplex
用处：在线求最小费用最大流（支持动态加边），支持负环，效率高
思路：在图中不断找负环，然后把他跑满。
他和线性规划中的单纯形法类似，以下是他的步骤：
- 加边 \(T\to S\)，容量 \(+\inf\)，费用 \(-\inf\)（而非 \(0\)）
- 随便找到一棵生成树，满足每条树边都有剩余流量。
- 枚举每一条边，判断他加入后是否产生负环，如果不产生负环就跳过。
- 找到这条边两端点在树上的 LCA，并找出环上流量最小的边，存下整个环。
- 更新环上流量、答案费用，删去流量最小边，加入这条边，再调整边顺序，构成新的生成树。
- 回到第 3 步直到没有负环为止。
- 最大流是第 1 步所加边的流量，最小费用要加上最大流 \(\times\inf\)。
如何快速判负环？每个点维护到根路径和即可 \(O(1)\) 判。
正确性：由第 1 步保证了。
注意到他的步骤和“LCT维护最小生成树”有点类似。
- 最小费用可行流：第 1 步加边的费用为 \(0\)、反边容量为 \(\inf\)，第 7 步最小费用不变即可。
- 最小费用最小流：事先
swap(s, t)即可。
int nw, fa[N], fe[N], cir[N], tag[N];
ll sum[N];
void DFS(int u, int f, int c) {
fa[u] = e[f].u, fe[u] = f, tag[u] = c;
for (int i = h[u]; i; i = e[i].n)
if (e[i].w && tag[e[i].v] != c) DFS(e[i].v, i, c);
}
ll Sum(int u) {
if (tag[u] == nw) return sum[u];
return tag[u] = nw, sum[u] = Sum(fa[u]) + e[fe[u]].c;
}
ll Push(int o) {
int cnt = 0, del = 0, P = 2;
ll C = 0, F = e[o].w;
++nw;
int p = e[o].u, lca = e[o].v;
while (p) tag[p] = nw, p = fa[p];
while (tag[lca] != nw) tag[lca] = nw, lca = fa[lca];
for (int u = e[o].u; u != lca; u = fa[u]) {
cir[++cnt] = fe[u];
if (F > e[fe[u]].w) F = e[fe[u]].w, del = u, P = 0;
}
for (int u = e[o].v; u != lca; u = fa[u]) {
cir[++cnt] = fe[u] ^ 1;
if (F > e[fe[u] ^ 1].w) F = e[fe[u] ^ 1].w, del = u, P = 1;
}
cir[++cnt] = o;
rep(i, 1, cnt) C += F * e[cir[i]].c, e[cir[i]].w -= F, e[cir[i] ^ 1].w += F;
if (P == 2) return C;
int u = e[o].u, v = e[o].v;
if (P == 1) swap(u, v);
int lste = o ^ P, lstu = v, tmp;
while (lstu != del) {
swap(fe[u], lste ^= 1), --tag[u];
tmp = fa[u], fa[u] = lstu, lstu = u, u = tmp;
}
return C;
}
void Simplex() {
eadd(t, s, INF, -INF);
DFS(t, 0, ++nw);
tag[t] = ++nw, fa[t] = 0;
ll F = 0, C = 0;
int ok = 1;
while (ok) {
ok = 0;
rep(i, 2, tot)
if (e[i].w && e[i].c + Sum(e[i].u) - Sum(e[i].v) < 0)
C += Push(i), ok = 1;
}
F = e[tot].w;
C += e[tot].w * INF;
cout << F << '\n' << C << '\n';
}