跳转至

费用流

对于一个网络图 \(G=(V,E)\)，每条边都被额外赋予了一个权值：费用 \(c(u,v)\)。一个流的总费用是 \(\sum_{(u,v)\in E}{f(u,v)c(u,v)}\)。

一般情况，我们希望在最大流的前提下，最小化流的费用，称为最小费用最大流。

求解费用流

求解费用流的方法仍然是增广路算法。这个算法要求网络图初始时没有负圈。

引理

如果每次增广时都选择路径费用最小的增广路，那么求出的一定是费用最低的最大流。

证明

考虑归纳法。记 \(f_i\) 表示流量为 \(i\) 时的最小费用。我们在 \(f_i\) 的基础上添加一条流量为 \(1\) 的增广路，得到 \(f_{i+1}\)。假设 \(f'_{i+1}\) 是比 \(f_{i+1}\) 费用更低的流，由于 \(f_{i+1}-f_i\) 已经是最短的增广路了，因此 \(f_{i+1}-f_i\) 一定至少包含一个负圈。那么，\(f_i\) 就不是费用最小的流，因为我们可以给这个负圈增加流量，减少费用。

由此我们可以得到：如果网络初始时不包含负圈，则经过若干轮增广后，仍然不包含负圈，并且一定是最小费用流。

根据引理，我们可以使用 Dinic+spfa 实现最小费用最大流。

模板代码 P3381 【模板】最小费用最大流

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
using namespace std;
const int N = 5e3 + 10;
const int M = 5e4 + 10;
const int INF = (int)0x3f3f3f3f3f3f3f3f;

struct Edge {
    int v, w, c;
    int next;
} pool[2 * M];
int ne = 1, head[N];

void addEdge(int u, int v, int w, int c) {
    pool[++ne] = {v, w, c, head[u]};
    head[u] = ne;
}

int n, m, s, t;

namespace dinic {
    int dis[N], dep[N], vis[N], now[N];
    int que[M], hd, tl;
    int ans;
    bool spfa() {
        for(int i = 1; i <= n; i++) {
            vis[i] = 0;
            dis[i] = INF;
            now[i] = head[i];
        }
        hd = 1, tl = 0;
        que[++tl] = s;
        dis[s] = 0;
        while(hd <= tl) {
            int u = que[hd++];
            vis[u] = 0;
            for(int i = head[u]; i; i = pool[i].next) {
                int v = pool[i].v, w = pool[i].w, c = pool[i].c;
                if(w && dis[u] + c < dis[v]) {
                    dis[v] = dis[u] + c;
                    dep[v] = dep[u] + 1;
                    if(vis[v]) continue;
                    vis[v] = 1;
                    que[++tl] = v;
                }
            }
        }
        return dis[t] != INF;
    }
    int dfs(int u, int sum, int cost) {
        if(u == t) {
            ans += sum * cost;
            return sum;
        }
        int flow = 0;
        for(int i = now[u]; i && sum; i = pool[i].next) {
            int v = pool[i].v, w = pool[i].w, c = pool[i].c;
            now[u] = i;
            if(!w || dep[v] != dep[u] + 1 || dis[v] != dis[u] + c || vis[v]) continue;
            int k = dfs(v, min(sum, w), cost + c);
            if(!k) dis[v] = 0;
            else {
                pool[i].w -= k;
                pool[i ^ 1].w += k;
                sum -= k;
                flow += k;
            }
        }
        return flow;
    }
    void calc() {
        int flow = 0;
        while(spfa()) flow += dfs(s, INF, 0);
        cout << flow << ' ' << ans << endl;
    }
}

int main() {

    cin >> n >> m >> s >> t;
    for(int i = 1; i <= m; i++) {
        int u, v, w, c;
        cin >> u >> v >> w >> c;
        addEdge(u, v, w, c);
        addEdge(v, u, 0, -c);
    }

    dinic::calc();

    return 0;
}

费用流建模

待完善