跳转至

费用流

不同于普通最大流的流网络，费用流的流网络中每条边还有一个费用 \(c(u, v)\)，一个流 \(f\) 的费用定义为 \(c(f) = \displaystyle\sum_{u \in \mathbf V}\sum_{v \in \mathbf V} f(u, v) c(u, v)\)。我们要求出流是最大流时的最小（大）费用（下文仅说明最小费用流，最大费用流可以将所有边的费用变为相反数，转化为求最小费用流，再将答案变为相反数）。

SSP 算法

SSP 算法类似于增广路径求最大流的算法。我们定义残量网络中的费用：

\[ c_f(u, v) = \begin{cases} c(u, v), &(u, v) \in \mathbf E \\ -c(u, v), &(v, u) \in \mathbf E \\ 0, &\text{otherwise} \\ \end{cases} \]

如果基于 Dinic 求最大流，那么需要将每次 BFS 分层改成求残量网络中的最短路，其中以 \(c_f(u, v)\) 为边权（我们认为 \(w_f(u, v) = 0\) 的边不在残量网络中）。增广的过程中只能增广最短路。

消圈定理

定义负圈为残量网络中的负环。

对于两个流 \(f_1, f_2\)，定义 \((f_1 - f_2)(u, v) = f_1(u, v) - f_2(u, v)\)。可以看出，\(f_1 - f_2\) 满足流量守恒。

消圈定理

流 \(f\) 是流量为 \(\mid f \mid\) 的最小费用流 \(\iff\) 残量网络 \(G_f\) 中不存在负圈

证明

充分性：使用反证法。若流 \(f\) 是流量为 \(\mid f \mid\) 的最小费用流，且残量网络 \(G_f\) 中存在负圈，那么可以在不增加流量的情况下增加负圈上的权值，同时费用减少，与假设矛盾。

必要性：考虑证明其逆否命题，即若流 \(f\) 不是流量为 \(\mid f \mid\) 的最小费用流时，残量网络 \(G_f\) 中存在负圈。若存在 \(f'\) 使 \(c(f') < c(f), \mid f \mid = \mid f' \mid\)。因为 \(\mid f \mid = \mid f' \mid\)，所以 \(f' - f\) 中源、汇点的流量都是 \(0\)。因为 \(f' - f\) 也满足流量守恒，且 \(f', f\) 一定不同，所以 \(f' - f\) 一定是由若干环组成（如果有链，因为源、汇点的流量为 \(0\)，链的端点一定不满足流量守恒）。同时，因为 \(c(f') < c(f)\)，\(f' - f\) 中一定至少存在一个负圈。因此 \(f\) 中存在负圈（可以用 \(f' = f + (f' - f)\) 来理解，能在 \(f\) 上增广 \(f' - f\)，就说明 \(f\) 中也有 \(f' - f\) 中的负圈）。

正确性证明

证明可能有问题

因为 SSP 算法仍然使用增广路径求最大流，由最大流最小割定理，SSP 算法能求出最大流。

接下来证明能求出最小费用。使用数学归纳法和反证法。设最大流为 \(F\)，假设已知 \(f_i\) 为 \(\mid f_i \mid = i\) 时的最小费用流，其中 \(0 \leq i < F\)。已知 \(c(f_0) = 0\)，且此时残量网络中不存在负圈。

令 \(f_{i + 1}\) 为 \(f_i\) 增广一条残量网络中的最短路径后的流。若存在一个流 \(f'\) 使 \(\mid f' \mid = \mid f_{i + 1} \mid, c(f') < c(f_{i + 1})\)，\(f' - f_i\) 中一定有负圈（因为 \(c(f') < c(f_{i + 1})\)，也就是说 \(f'\) 只能是由 \(f_i\) 增广一条路径后再增广负圈得到），也就是说 \(f_i\) 中一定有负圈。由消圈定理，与假设 \(f_i\) 为最小费用流矛盾，因此 \(f_{i + 1}\) 就是最小费用流。

Bug

Dinic 费用流的正确性证明待完善。

负圈

在使用 SSP 算法求费用流时，由于每次增广出来的都是最小费用流，所以在求解过程中不会出现负圈。唯一出现负圈的情况是原网络中有负圈，在第一次 SPFA 时会陷入死循环。因此 SSP 算法只能处理原图中没有负圈的费用流。

时间复杂度

若最大流为 \(f\)，则时间复杂度为 \(O(\mid \mathbf V \mid \mid \mathbf E \mid \mid f \mid)\)，是伪多项式时间，但在 OI 中几乎不可能达到这个上界。

Bug

当前内容待完善。

代码

代码 
 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
#include <cstring>
#include <iostream>
#include <queue>
#define TO(x) edge[x].to
#define W(x) edge[x].w
#define C(x) edge[x].c
#define NXT(x) edge[x].nxt
using namespace std;
typedef pair<int, int> pii;
const int MAXN1 = 5005, MAXN2 = 5e4 + 5, INF = (1ll << 31) - 1;
int n, m, s, t;
class Graph {
private:
    struct Edge {
        int to, w, c, nxt;
        Edge() {}
        Edge(int to, int w, int c, int nxt) : to(to), w(w), c(c), nxt(nxt) {}
    };
    int tot, cost, dis[MAXN1], cur[MAXN1], head[MAXN1];
    bool vis[MAXN1];
    Edge edge[MAXN2 << 1];
    bool spfa() {
        memcpy(cur, head, sizeof(cur));
        queue<int> q;
        for (int i = 1; i <= n; ++i)
            dis[i] = INF;
        for (dis[s] = 0, q.emplace(s); !q.empty(); vis[q.front()] = false, q.pop())
            for (int e = head[q.front()]; e; e = NXT(e))
                if (W(e) && dis[TO(e)] > dis[q.front()] + C(e)) {
                    dis[TO(e)] = dis[q.front()] + C(e);
                    if (!vis[TO(e)])
                        q.emplace(TO(e)), vis[TO(e)] = true;
                }
        return dis[t] < INF;
    }
    int dfs(int x, int flow) {
        if (x == t)
            return flow;
        vis[x] = true;
        int now = flow;
        for (int &e = cur[x]; e; e = NXT(e))
            if (W(e) && !vis[TO(e)] && dis[TO(e)] == dis[x] + C(e)) {
                int f = dfs(TO(e), min(W(e), now));
                W(e) -= f, W(e ^ 1) += f, now -= f, cost += f * C(e);
                if (!now)
                    break;
            }
        return vis[x] = false, flow - now;
    }

public:
    Graph() { tot = 1; }
    void addEdge(int u, int v, int w, int c) {
        edge[++tot] = Edge(v, w, c, head[u]), head[u] = tot;
        edge[++tot] = Edge(u, 0, -c, head[v]), head[v] = tot;
    }
    pii solve() {
        cost = 0;
        int ans = 0;
        while (spfa())
            ans += dfs(s, INF);
        return {ans, cost};
    }
} graph;
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m >> s >> t;
    for (int i = 1, u, v, w, c; i <= m; ++i)
        cin >> u >> v >> w >> c, graph.addEdge(u, v, w, c);
    pii ans = graph.solve();
    cout << ans.first << " " << ans.second << "\n";
}

注意事项

Tip

  • 最短路算法需要用 SPFA，因为有负权边；且每次 SPFA 需要跑完，而不是松弛到汇点就结束。
  • 为了处理 \(0\) 环，需要记录 vis 数组，防止在一条增广路上出现一个点多次。同时为了使当前弧优化发挥作用，需要在 DFS 结束时将 vis 设为 false。

当前弧优化的奇妙事实

在下面的讨论中，我们将不在 DFS 结束时恢复 vis 数组的实现称为 vis 优化。在使用 vis 优化的时候，当前弧优化无法发挥作用，所以在 vis 优化时不需要写当前弧。

一般情况下，当前弧优化和 vis 优化耗时差不多，但在 loj 的模板题中，使用 vis 优化耗时比当前弧优化耗时少 \(200 \text{ms}\) 左右，但经过大样例的测试，发现当前弧优化的 SPFA 次数、DFS 次数和链式前向星跳边次数均比 vis 优化少。

动态建图

在美食节中，我们需要使用动态建图，但这道题的动态建图需要我们增广完一条路径之后加边，而不是跑完一次费用流之后再加边。在这种情况下，我们不能使用 Dinic，只能使用 EK，即每次 SPFA 之后只能增广一条路径。

为了解释，我们假设走完增广路 A 后需要加边 C，走完增广路 B 后需要加边 D，且 A 是当前最短路，B 是当前次短路。如果使用 Dinic，可能会出现增广完 AB 后一起加边 CD 的情况。如果增广完 A 并加边 C 后，B 不再是当前最短路（即现在的最短路经过 C），此时增广 B 之后不再是最小费用流，根据消圈定理，当前残量网络里有负圈，因此必须走完增广路之后立刻加边并重跑 SPFA。

对于最大流的问题，如果当前增广的不是最短路并不会使结果错误，也不会运行错误；但对于费用流，每次必须增广最短路，否则残量网络中就会存在负圈，把 SPFA 卡住，同时也意味着当前流不是最小费用流，因此在费用流的动态建图问题中需要注意这点。