介绍

最小费用最大流，简称 费用流。

与 最大流 不同的是，每条边还有一个 费用 \(c\)，这条边每流过一个单位流量，就需要付出 \(c\) 的费用。

在保证最大流的 前提 下，还要让总费用最小。

算法

费用流，常用的为 SSP（Successive Shortest Path）算法。

此算法不能处理带负环的情况，需使用消圈法。

它是一个贪心的算法，思路是每次寻找单位费用最小的增广路进行增广，直到图上不存在增广路为止。

证明

我们考虑使用数学归纳法和反证法来证明 SSP 算法的正确性。

设流量为 \(i\) 的时候最小费用为 \(f_i\)。我们假设最初的网络上 没有负圈，这种情况下 \(f_0=0\)。

假设用 SSP 算法求出的 \(f_i\) 是最小费用，我们在 \(f_i\) 的基础上，找到一条最短的增广路，从而求出 \(f_{i+1}\)。这时 \(f_{i+1}-f_i\) 是这条最短增广路的长度。

假设存在更小的 \(f_{i+1}\)，设它为 \(f_{i+1}'\)。因为 \(f_{i+1}-f_i\) 已经是最短增广路了，所以 \(f'_{i+1}-f_i\) 一定对应一个经过 至少一个负圈 的增广路。

这时候矛盾就出现了：既然存在一条经过至少一个负圈的增广路，那么 \(f_i\) 就不是最小费用了。因为只要给这个负圈添加流量，就可以在不增加 \(s\) 流出的流量的前提下，使 \(f_i\) 对应的费用更小。

综上，SSP 算法可以正确求出无负圈网络的最小费用最大流。

证明过程摘自 OI-Wiki：SSP 算法

复杂度分析

如果使用 spfa 求解最短路，每次找增广路的时间复杂度为 \(O(nm)\)。设该网络的最大流为 \(f\)，则最坏时间复杂度为 \(O(nmf)\)。事实上，SSP 算法是 伪多项式时间。

实现

Dinic + spfa:

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 <cstdio>
#include <cstring>
#include <ios>
#include <iostream>
#include <queue>
using namespace std;
const int N = 5e3 + 5, M = 5e4 + 5;
using ll = long long;
const ll inf = 1e18;
struct graph {
    struct edge {
        int v, nt;
        ll c, w;
    } e[M << 1];
    int hd[N], tot = 1;
    void add(int u, int v, ll c, ll w) {
        e[++tot].v = v, e[tot].nt = hd[u], e[tot].c = c, e[tot].w = w, hd[u] = tot;
    }
    void uadd(int u, int v, ll c, ll w) { add(u, v, c, w), add(v, u, 0, -w); }
} g;
int n, m, s, t;
namespace SSAP {
bool vis[N];
int cur[N];
ll dis[N];
queue<int> q;
bool spfa() {
    for (int i = 1; i <= n; i++) dis[i] = inf, vis[i] = false;
    dis[s] = 0, vis[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = g.hd[u]; i; i = g.e[i].nt) {
            int v = g.e[i].v;
            if (dis[v] > dis[u] + g.e[i].w && g.e[i].c) {
                dis[v] = dis[u] + g.e[i].w;
                if (!vis[v]) q.push(v), vis[v] = true;
            }
        }
    }
    return dis[t] != inf;
}
ll mincost;
ll dfs(int u, ll f) {
    if (u == t || f == 0) return f;
    vis[u] = true;
    ll sum = 0;
    for (int &i = cur[u]; i; i = g.e[i].nt) {
        int v = g.e[i].v;
        cur[u] = i;
        if (!vis[v] && dis[v] == dis[u] + g.e[i].w && g.e[i].c) {
            ll t = dfs(v, min(f, g.e[i].c));
            if (t) {
                g.e[i].c -= t, g.e[i ^ 1].c += t;
                mincost += g.e[i].w * t;
                sum += t, f -= t;
                if (f == 0) break;
            }
        }
    }
    return sum;
}
ll flow() {
    ll ans = 0, flow;
    while (spfa()) {
        for (int i = 1; i <= n; i++) cur[i] = g.hd[i], vis[i] = false;
        while ((flow = dfs(s, inf))) {
            ans += flow;
            for (int i = 1; i <= n; i++) vis[i] = false;
        }
    }
    return ans;
}
} // namespace SSAP
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++) {
        int u, v;
        ll c, w;
        cin >> u >> v >> c >> w;
        g.uadd(u, v, c, w);
    }
    ll ans = SSAP::flow();
    cout << ans << " " << SSAP::mincost << endl;
    return 0;
}