题解 P3381 【【模板】最小费用最大流】

## 费用流 ### 做法 1. 在残余网络上寻找最短路 2. 对该路径进行增广, 对答案产生贡献 3. 不断重复opt.1操作, 直至$s\to t$不存在路径 ### 证明 #### 定义 1. 定义$f$作为图中的流 2. $f\text{-}g$表示流$f$与流$g$之间不同的流量 3. $in(u)$表示$u$的入流, $out(u)$表示$u$的出流 #### Proof 1 - $f$是最小费用流 $\Leftrightarrow$ 残余网络中无负圈 假设, 存在费用比$f$更小的流$f'$. 观察二者, 由于流量相同, 那么$out(s), in(t)$均相同 且$\forall u, in(u)=out(u)$ 在$f, f'$中恒成立. **于是$f'\text{-}f$形成的流是由若干圈组成的!** 因为$cost(f') < cost(f)$ 故$f $的残留网络中存在至少一个负圈. #### Proof 2 - 利用数学归纳证明 假设$f_i$ 表示流量为$i$的最小费用流 $f_0$便是原图(显然原图中不存在负圈). 那么根据我们的做法, 得到了$f_{i+1}$, 那么假设存在费用更小的流$f_{i+1}'$ 则 $f_{i + 1} \text{-}f_i$是一条$s\to t$的**最短路**, 而$f_{i+1}'\text{-}f_i$是一条$s\to t$的路径与若干圈组成的 那么这些圈中则必定存在负圈, 这与$f_i$是最小费用流相悖. 故上述成立. --- ### 原始对偶算法 ~~不要在意名字~~ > 背景: 图中存在负权边, ~~spfa已经死了~~ > > 思考: 求最短路可否用Dijkstra呢? 假如我们给每一个节点 附上**势** $h(i)$：使得$e(u,v)' = e(u,v) + h(u) - h(v)$ 且它恒非负, 那就可以用$\text{Dijkstra}$了 - 考虑最短路的性质: $dis(u) + e(u, v) \geq dis(v)$ 得到$dis(u)-dis(v) + e(u, v) \geq 0$ 那么我们将$dis(u)-dis(v) + e(u, v)$作为新的边权, 记为$e(u,v)'$ ~~不难证明~~以它为新图所得到的最短路与原图的最短路经过路径是一样的. 那么这样就意味着我们可以$\text{Dijkstra}$了. (~~比spfa~~不知道高到哪里去了, 雾 即: 在跑no.i次增广的时候的势$h_i(u)$为$dis_i(u)$ ~~等等, 如果我们已经知道了势(即最短路), 那还tm要增广干嘛~~ 于是发现其实$h_i(u)=h_{i-1}(u)$也是可以的, 即变成上次增广的**原图**中$u$的最短路. > 从简证明: > > 1. 若e(u,v)在no.i-1次增广时存在, 那么显然满足 > > 2. 若e(u,v)在no.i-1次增广不存在 > > 那么此次它的出现是因为增广导致的 > > 意思就是说它一定在上次的$s\to t$的最短路上, 那么e(u, v) = -e(v, u) = 0 > > 依旧非负. ```cpp %:pragma GCC optimize("Ofast", 2) #include <bits/stdc++.h> using namespace std; namespace { inline void read(int &x) { x = 0; int f = 1; char c = getchar(); for(; !isdigit(c); c = getchar()) if(c == '-') f = -1; for(; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ '0'); x *= f; } } const int N = 5e3 + 5, M = 5e4 + 5; const int inf = 1e9; # define pi pair<int, int> int n, m, s, t, u, v, c, w; namespace Primal { int Ecnt = 1, first[N], nex[M * 2], arr[M * 2], cap[M * 2], cost[M * 2]; int dis[N], h[N], pree[N], prev[N], F, C; template <typename T> inline void Min(T &a, T b) { if(a > b) a = b; } inline void Ad(int u, int v, int c, int w) { nex[++Ecnt] = first[u], first[u] = Ecnt, arr[Ecnt] = v, cap[Ecnt] = c, cost[Ecnt] = w; } inline void add(int u, int v, int c, int w) { Ad(u, v, c, w), Ad(v, u, 0, -w); } void Dijkstra() { static priority_queue<pi, vector<pi>, greater<pi> > q; for(; !q.empty(); q.pop()); fill(dis, dis + 1 + n, -1); dis[s] = 0, q.push(pi(0, s)); // printf("-----------\n"); while(!q.empty()) { pi now = q.top(); q.pop(); int u = now.second; if(dis[u] < now.first) continue; for(int i = first[u]; i; i = nex[i]) { static int v; v = arr[i]; if(!cap[i]) continue; if(dis[v] < 0 || dis[v] > dis[u] + cost[i] + h[u] - h[v]) { dis[v] = dis[u] + cost[i] + h[u] - h[v]; prev[v] = u, pree[v] = i; q.push(pi(dis[v], v)); } } } } pi solve(int s, int t) { fill(h, h + 1 + n, 0); for(int f = inf; f > 0; ) { Dijkstra(); if(dis[t] < 0) break; for(register int i = 1; i <= n; ++i) // be careful this for h[i] += (dis[i] != -1) ? dis[i] : 0; int d = f; for(int u = t; u != s; u = prev[u]) Min(d, cap[pree[u]]); f -= d, F += d, C += h[t] * d; assert(C >= 0); for(int u = t; u != s; u = prev[u]) { cap[pree[u]] -= d; cap[pree[u] ^ 1] += d; } } return pi(F, C); } } using namespace Primal; int main() { read(n), read(m), read(s), read(t); for(int i = 1; i <= m; ++i) { read(u), read(v), read(c), read(w); add(u, v, c, w); } pi get = solve(s, t); printf("%d %d\n", get.first, get.second); return 0; } ``` 其实大家可能最疑惑的就是为什么有代码是 ： ```cpp for(int i = 1; i <= n; ++i) h[i] += dist[i]; ``` 从理论出发, $h'(i)$此时定义为no.(i-1)次增广时**原图**中的最短路 ~~(再次强调是原图!)~~ 而数组dist实际存储的是 $$ \begin{aligned} \text{dist[u]}&=\sum e'(u, v) \\ &=\sum \bigg( h(u)-h(v) + e(u, v) \bigg) \\ &= dis(u) + h(s)-h(u) \\ &= dis(u) - h(u) \\ \end{aligned} $$ 那么$h'(u) = dis(u) = h(u) + dist[u]​$ 所以就是 一直都是 "+="