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

费用流

做法

1. 在残余网络上寻找最短路
2. 对该路径进行增广, 对答案产生贡献
3. 不断重复opt.1操作, 直至s\to t不存在路径

证明

定义

1. 定义f作为图中的流

Proof 1

假设, 存在费用比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_{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

   依旧非负.

%: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;
}

其实大家可能最疑惑的就是为什么有代码是 ：

   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]​

所以就是 一直都是 "+="