本文介绍简单的网络流模型和相关算法，关于网络流的基础应用，见网络流应用专题。
        2020.2.9更新可行流等进阶部分。

        给定源点s和汇点t，中间有若干条结点做中转，有向边表示转运方向，权值代表最大容量。在这样的图下，汇点最多能够接收到的流量最大值是多少？这就是网络流的最大流问题。
        下图就是一个网络流的模型图（来自刘汝佳紫书，有改动）：

网络流最大流问题的三个性质

        对于每一条边，它的最大流量转运上限称为容量（capacity），而这条边上的实际转运量称为流量（flow）。在最大流问题中，有三个基本性质：

  • 容量限制：对于任意一条边(u,v)，总是有f(u,v)≤c(u,v)，即流量不可大于容量。
  • 反对称性：f(u,v)=-f(v,u)。理解：把x个物品从u送到v就是把-x个物品从v送到u，-x可以用来描述有多少流量流到该结点。
  • 流量平衡：对于除了源点和汇点的点，总有$\sum f(u,v)=0$（流入流出均衡）。

        任何一种转运方案都需要满足上面三个性质。

残量网络

        下面给出了一种转运方案，红色代表实际流量：

        容易验证，这个流量设置满足前文提到的三个性质，这时汇点总流量为16，但是这不一定是最大流量。将每一条边权值变成容量与实际流量之差，可以得到：

        现在的边权代表“这条边还可以流过多少”，一个很直观的想法是：找到一条从s到t的路径，如果这条路上所有边的边权都大于0，那么总流量还可以加上路径上边权的最小值（注：这种路称为增广路）。比如我们发现走上面的三条边（边权为4、4、8）可以从s走到t，故总流量再加上4成为20，更新网络图，变成：

        不断这样找，直到找不到增广路，得到的就是最大流吗？事实证明这种方法是错的。这是因为，我们的思路是尽可能地利用每一条边的价值，让它的流量尽可能地接近容量。因此在某一条边的流量确定时，它的流量就只能只增不降了。比如，按照这个算法，我们不可能让V1->V3的流量减小（也就是残量增大）。
        问题来了，我们为什么要让好好的流量减小？让流量尽可能大不是更优吗？这只是直观上的感受，但事实上是错的，比如下面这个图（从网上找的图）：

        最大流显然是沿s->V1->t和s->V2->t时得到的2。可以发现，V1->V2的边连用都没用上，如果我们上来就把这条边用了（也就是流量为１），而它不能被减小，就只能得到错误的答案。
        所以应该有一个可以将边流量减小（也就是怼回去）的机制。
        如何解决？方法是给每一条边引入对应的反向边，反向边权值就是正向边已用的流量。上文已经说明反对称性，可以把反向边权值理解成反向的残量（反向走不通，容量为0，而流量为负）。原边（原有的边）权值表示这条路还可以走多少流量，反边权值表示这条路最多可以“反悔”多少流量。走正向边就是给这条边增加流量，走反向边就是给这条边减少流量。
        给每一条边建立与之对应的反向边，并规定正向边权值为容量与流量之差，反向边权值为正向边流量，就得到了残量网络(residual network)。对于重边，我们可以不将它们合并，得到的结果是一样的。一开始的例子可以建立如下的残量网络：

        于是有著名的增广路定理：

【增广路定理】当且仅当残量网络中不存在增广路时，此时的流是s->t的最大流。

EK算法

        给出一个图，我们建立它的残量网络图，不断寻找增广路更新最大流即可。如何寻求增广路？一个方法是BFS，这就是Edmonds-Karp算法（EK算法）。它的思想是不断用BFS找增广路，直到找不到为止。凡是找到一条，立即更新最大流和对应的边权。
        下面有一个小技巧：每找到一条边，立即建立它对应的反向边。将边从0开始标号，那么0和1是一对正向边和反向边，2和3也是一对…这样对于编号为x的边，它对应的反向边编号就是x^1，反向边找正向边也是这种方法。
        下面给出洛谷P3376模板题的EK算法代码。

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
#include<iostream>
#include<queue>

using namespace std;
struct {
    int to, next, v;
} edge[100000 * 2];
int head[10005], cnt = 0, n, m, b, e, pre[10005], flow[10005], ans = 0;//pre是点的前导边标号
queue<int> que;

inline void add(int x, int y, int z) {
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = z, head[x] = cnt++;
}

int BFS() {
    while (!que.empty())que.pop();
    for (int i = 1; i <= n; i++)pre[i] = -1;
    pre[b] = 0;
    que.push(b), flow[b] = 0x7fffffff;//flow是到这个流的最小边权
    while (!que.empty()) {//BFS每次只找一个增广路
        int f = que.front();
        if (f == e)break;//到达汇点，立即结束
        que.pop();
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && pre[edge[i].to] == -1) {
                pre[edge[i].to] = i, flow[edge[i].to] = min(flow[f], edge[i].v), que.push(edge[i].to);
            }
        }
    }
    if (pre[e] == -1)return -1;//没有增广路
    return flow[e];//返回途径的最小权值
}

int main() {
    cin >> n >> m >> b >> e;
    for (int i = 1; i <= n; i++)head[i] = -1;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, 0);//加边，后边是反向边，权值为0
    }
    int increase;
    while ((increase = BFS()) != -1) {//直到找不到反向边
        int p = e;
        while (p != b) {//回退找路
            edge[pre[p]].v -= increase, edge[pre[p] ^ 1].v += increase;
            p = edge[pre[p] ^ 1].to;//更新边权值：前导边减去流量，对应的反边加上流量
        }
        ans += increase;//更新答案
    }
    cout << ans << endl;
    return 0;
}

Dinic算法

        可以发现EK算法效率的确不高，原因就在于进行了太多次BFS，每次只找一条增广路。这于是就有了Dinic算法。
        Dinic算法基于分层图思想，它的算法步骤是：

  1. 从源点开始给图用BFS分层。每一次只能走边权大于0的边，得到到源点的最小边距。（源点层次序号为0）
  2. 从源点开始DFS，找到在当前分层图下的所有增广路。在当前分层图下的含义是：只能走边权大于0的边并且出点深度必须为该点深度加一。每找到一条更新权值和流量。
  3. 回到第一步继续分层，直到汇点不再与源点连通（也就是没法从源点开始获得汇点深度）。
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
#include<iostream>
#include<queue>

#define N 10005
using namespace std;
struct {
    int to, next, v;
} edge[100000 * 2];
int head[N], cnt = 0, n, m, b, e,  ans = 0, deep[N];
queue<int> que;

inline void add(int x, int y, int z) {
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = z, head[x] = cnt++;
}

int DFS(int x, int limit) {//DFS找增广路，x是当前结点编号，limit是目前的最小边权。返回能够得到的流值（就是还可以扩展多少）
    if (limit == 0 || x == e)return limit;//最小边权为0或者到汇点，不能再继续走，直接返回。
    int f, flow = 0;
    for (int i = head[x]; ~i; i = edge[i].next) {
        if (deep[edge[i].to] == deep[x] + 1 && (f = DFS(edge[i].to, min(limit, edge[i].v)))) {//深度满足并且出点能够找到的流值非0，这里已经排除掉了权值为0的边
            edge[i].v -= f, edge[i ^ 1].v += f, flow += f, limit -= f;//修改限制，flow加上这个分枝的流值
            if (!limit)break;//最小值到0，无法再继续
        }
    }
    return flow;//返回流值
}

bool BFS() {//用于分层
    while (!que.empty())que.pop();
    for (int i = 1; i <= n; i++)deep[i] = n;//全部初始化为n
    deep[b] = 0, que.push(b);//源点入队，深度为0
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && deep[edge[i].to] == n) {
                deep[edge[i].to] = deep[f] + 1, que.push(edge[i].to);
                if (edge[i].to == e)return true;//汇点找到，返回true
            }
        }
    }
    return deep[e] != n;
}

int main() {
    cin >> n >> m >> b >> e;
    ans = 0;
    for (int i = 1; i <= n; i++)head[i] = -1;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, 0);
    }
    while (BFS())ans += DFS(b, 0x7fffffff);//每一次都加上可以得到的流值
    cout << ans;
    return 0;
}

        Dinic算法就比较高效了，它可以AC掉上面提到的网络流模板题。这里还有一个优化：当前弧优化。
        可以发现上面DFS代码中的break条件是limit==0。如果循环成功地进入了下一条边，说明上一条边的limit没有用完！这说明上一条边“费尽全力”地找增广路已经达到了极限，那么从这条边再找就不可能有增广路了。于是这条边应该被“废弃”以提高效率。我们用cur记录应该从哪一条边开始以优化算法，注意每次BFS时应重置cur。
        下面是加入当前弧优化的Dinic算法代码：

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
#include<iostream>
#include<queue>

#define N 10005
using namespace std;
struct {
    int to, next, v;
} edge[100000 * 2];
int head[N], cnt = 0, n, m, b, e, ans = 0, deep[N], cur[N] = {0};
queue<int> que;

inline void add(int x, int y, int z) {
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = z, head[x] = cnt++;
}

int DFS(int x, int limit) {
    if (limit == 0 || x == e)return limit;
    int f, flow = 0;
    for (int i = cur[x]; ~i; i = edge[i].next) {//从cur开始
        cur[x] = i;//记录当前的边
        if (deep[edge[i].to] == deep[x] + 1 && (f = DFS(edge[i].to, min(limit, edge[i].v)))) {
            edge[i].v -= f, edge[i ^ 1].v += f, flow += f, limit -= f;
            if (!limit)break;
        }
    }
    return flow;
}

bool BFS() {
    while (!que.empty())que.pop();
    for (int i = 1; i <= n; i++)deep[i] = n, cur[i] = head[i];//重置cur
    deep[b] = 0, que.push(b);
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && deep[edge[i].to] == n) {
                deep[edge[i].to] = deep[f] + 1, que.push(edge[i].to);
                if (edge[i].to == e)return true;
            }
        }
    }
    return deep[e] != n;
}

int main() {
    cin >> n >> m >> b >> e;
    ans = 0;
    for (int i = 1; i <= n; i++)head[i] = -1;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, 0);
    }
    while (BFS())ans += DFS(b, 0x7fffffff);
    cout << ans;
    return 0;
}

ISAP算法

        下面介绍另一种算法：ISAP算法。这也是一种高效的求最大流的方法。Dinic算法不停地进行BFS重新分层，能不能便DFS边更新深度呢？这就是ISAP算法的思想。它的算法步骤是：

  1. BFS分层（这里是从汇点开始），只能走其反向边权值非0的边，相当于逆着正边走，得到深度。
  2. 从源点开始找增广路。事实上，我们经常用循环来进行这个过程。每次只能走边权非0并且深度为自身深度减一的出点，走到汇点时更新答案和边权。当该点没有任何合法出点时更新其深度。

        当源点深度大于或等于n（n为总结点数）时，不存在增广路。
        更新深度的方法：找到该点所有边权非0的出点，在它们的深度中取最小值，那么点深度更新为这个最小值加一。
        ISAP算法中有一个重要的优化：GAP优化。易知点的深度更新只能让深度不断变大，不可能变小。因此如果深度出现了断层（比如不存在深度为3的点，但是有深度为4和2的点），那么这个断层就不可能接上了（只有某深度为2的点找到一个深度也为2的出点并且边权非0才可能把深度更新成3，然而这种情况不可能发生）。根据我们点前进的顺序（深度递减）可知，源点必然在这个断层的前面，于是源点不可能再走到汇点了，判断出增广路不存在，直接break。这就是GAP优化。
        代码不理解就当板子记吧。

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
#include<iostream>
#include<queue>

#define N 10005
#define inf 1000000
using namespace std;
struct {
    int to, next, v;
} edge[100000 * 2];
int head[N], cnt = 0, n, m, b, e, ans = 0, deep[N], cur[N] = {0}, pre[N] = {0}, num[N] = {0};
queue<int> que;

inline void add(int x, int y, int z) {
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = z, head[x] = cnt++;
}

inline void BFS() {//判深度
    for (int i = 1; i <= n; i++)deep[i] = n, cur[i] = head[i];
    que.push(e), deep[e] = 0;
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i ^ 1].v > 0 && deep[edge[i].to] == n)deep[edge[i].to] = deep[f] + 1, que.push(edge[i].to);
        }
    }
}

int maxFlow() {//最大流统计
    int flow = inf, p = e;
    while (p != b) {
        flow = min(flow, edge[pre[p]].v), p = edge[pre[p] ^ 1].to;
    }
    p = e;
    while (p != b) {
        edge[pre[p]].v -= flow, edge[pre[p] ^ 1].v += flow, p = edge[pre[p] ^ 1].to;
    }
    return flow;
}

inline void ISPA() {
    int now = b;
    BFS();
    for (int i = 1; i <= n; i++)num[deep[i]]++;//深度数量统计
    while (deep[b] < n) {
        if (now == e) {//找到一条增广路
            ans += maxFlow();//更新
            now = b;//回到源点再找
        }
        bool flag = false;
        for (int i = cur[now]; ~i; i = edge[i].next) {
            if (deep[edge[i].to] == deep[now] - 1 && edge[i].v > 0) {
                flag = true, cur[now] = i, pre[edge[i].to] = i, now = edge[i].to;
                break;
            }
        }
        if (!flag) {//没有合法出点，更新深度
            int minn = n;
            for (int i = head[now]; ~i; i = edge[i].next)if (edge[i].v > 0)minn = min(minn, deep[edge[i].to]);
            num[deep[now]]--;
            if (num[deep[now]] == 0)break;//GAP优化！！
            deep[now] = minn + 1, num[deep[now]]++, cur[now] = head[now];//更新cur
            if (now != b)now = edge[pre[now] ^ 1].to;//更新完深度，回退到这个点的前继，源点不用回退。
        }
    }
}

int main() {
    cin >> n >> m >> b >> e;
    ans = 0;
    for (int i = 1; i <= n; i++)head[i] = -1;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, 0);
    }
    ISPA();
    cout << ans;
    return 0;
}

        算出了最大流，怎么得到最佳方案？通过每一条原边（所有偶数边）的权值代表残量（也可以反向边直接得出流量），然后就可以得到最优时的流量分配方案了。

最小割问题

        将网络流分成两个不相交点集S、T，使得s（源点）在S中，t（汇点）在T中。断开连接起点在S中终点在T中的所有原边，这时s和t不再连通，称这样的集合划分为一个割。割的容量定义为被断开边的容量之和，求最小割是一个与最大流联系紧密的问题。
        有定理：

【最小割最大流定理】最小割容量等于最大流。

        证明略。
        这样我们就可以求最小割容量了，但是如何求最小割呢？EK算法结束时，我们得到了很多flow，它们当中大于0的点就是S集，剩下的是T集。注意这种方法要求在每次BFS前要清空一下flow（全部初始化成0）。Dinic算法和ISAP算法的方案求法待以后更新。
        一个待验证的假说：求完最大流之后边权变为0的原边就是被割掉的边。

        最小割点数量也是经典问题，但是最小割最大流定理只适用于割边。我们可以将每一个点分成两个点，一个连接点的入边，另一个连接点的出边，并在两点间加一条容量为1的边（注意源点和汇点中间边的边权为无穷大，因为通常不能割这两个点），这样就把割点问题转化为割边问题。

费用流问题

        在原有图的基础上加入“费用”，总费用为单位费用乘以这条边的流量。得到最大流的方案很多，但是其中有一种花费最少。最小费用最大流问题也是一类重要问题。
        解决方法是将EK算法中的BFS改成SPFA，根据最短路径（将费用看成边权）来找增广路。它和普通的EK算法相比，有以下几点区别：

  • 边的属性增加了一个费用，反边的费用是正边的相反数
  • 普通EK算法的BFS中，pre一旦确定便不再改变。但费用流下需要改变。

        这样优先选择最短路增广，得到的一定是最优解。
        下面给出EK算法费用流问题的模板代码：

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
#include<iostream>
#include<queue>

using namespace std;
struct {
    int to, next, v, price;
} edge[100000 * 2];
int head[10005], cnt = 0, n, m, b, e, pre[10005], flow[10005], ans = 0, dict[10005], vis[10005], minCost = 0;
queue<int> que;

inline void add(int x, int y, int z, int p) {
    edge[cnt].price = p, edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = z, head[x] = cnt++;
}

int SPFA() {
    while (!que.empty())que.pop();
    for (int i = 1; i <= n; i++)flow[i] = dict[i] = 0x7ffffff, vis[i] = 0, pre[i] = -1;//初始化
    pre[b] = -1, vis[b] = 1, dict[b] = 0, que.push(b);
    while (!que.empty()) {
        int f = que.front();
        que.pop(), vis[f] = 0;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && dict[edge[i].to] > dict[f] + edge[i].price) {//注意：这里没有要求pre[edge[i].to]==-1的限制，因为前导边需要根据最短路径的改变而改变
                dict[edge[i].to] = edge[i].price + dict[f];
                pre[edge[i].to] = i, flow[edge[i].to] = min(flow[f], edge[i].v);
                if (vis[edge[i].to] == 0)que.push(edge[i].to), vis[edge[i].to] = 1;
            }
        }
    }
    if (pre[e] == -1)return -1;
    return flow[e];
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> b >> e;
    for (int i = 1; i <= n; i++)head[i] = -1;
    for (int i = 1; i <= m; i++) {
        int u, v, w, p;
        cin >> u >> v >> w >> p;
        add(u, v, w, p), add(v, u, 0, -p);
    }
    int increase;
    while ((increase = SPFA()) != -1) {
        int p = e;
        while (p != b) {
            edge[pre[p]].v -= increase, edge[pre[p] ^ 1].v += increase;
            p = edge[pre[p] ^ 1].to;
        }
        ans += increase;
        minCost += increase * dict[e];//加上费用
    }
    cout << ans << " " << minCost;
    return 0;
}

zkw费用流

        除了EK+SPFA的费用流算法，还有另一种算法比较常用，那就是zkw费用流算法。
        EK+SPFA是EK算法的修改版，每次只进行一次增广，效率比较低下。这里可以借鉴Dinic的多次增广思路得到zkw费用流算法，它在一些情况下比EK+SPFA更高效。
        zkw费用流很像Dinic算法。它将BFS改成SPFA并修改了标号过程，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline bool SPFA() {
    for (int i = 1; i <= n; i++)vis[i] = 0, dict[i] = 0x7fffffff;
    que.push(t), dict[t] = 0, vis[t] = 1;//与Dinic不同的是，zkw费用流反向编号，即从汇点开始
    while (!que.empty()) {
        int f = que.front();
        que.pop(), vis[f] = 0;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i ^ 1].v > 0 && dict[edge[i].to] > dict[f] + edge[i ^ 1].price) {//走反边
                dict[edge[i].to] = dict[f] + edge[i ^ 1].price;
                if (!vis[edge[i].to])que.push(edge[i].to), vis[edge[i].to] = 1;
            }
        }
    }
    return dict[s] != 0x7fffffff;
}

        按道理，DFS过程就应该修改成：
1
2
3
4
5
6
7
8
9
10
11
int DFS(int x, int limit) {
    if (x == t || limit == 0)return limit;
    int f, flow = 0;
    for (int i = head[x]; ~i; i = edge[i].next) {
        if (dict[edge[i].to] == dict[x] - edge[i].price && (f = DFS(edge[i].to, min(limit, edge[i].v)))) {
            edge[i].v -= f, edge[i ^ 1].v += f, limit -= f, flow += f, ans += f * edge[i].price;//ans记答案
            if (limit == 0)break;
        }
    }
    return flow;
}

        这样做没什么错，只是会导致DFS递归次数过多，可能会RE或MLE。为解决这个问题，我们在DFS时规定每一个点只能遍历一次，这样就可以得到下面的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int DFS(int x, int limit) {
    if (x == t || limit == 0) {
        vis[x] = 1;
        return limit;
    }
    int f, flow = 0;
    vis[x] = 1;//用vis数组标记已被访问
    for (int i = head[x]; ~i; i = edge[i].next) {
        if (vis[edge[i].to] == 0 && dict[edge[i].to] == dict[x] - edge[i].price && (f = DFS(edge[i].to, min(limit, edge[i].v)))) {
            edge[i].v -= f, edge[i ^ 1].v += f, limit -= f, flow += f, ans += f * edge[i].price;
            if (limit == 0)break;
        }
    }
    return flow;
}

        和Dinic相同，在主函数中，这样去用：
1
while (SPFA()) flow += DFS(s, 0x7fffffff);

        为进一步提高效率，可以使用下面的方式：
1
2
3
4
while (SPFA()) {
        do memset(vis, 0, sizeof(vis)), flow += DFS(s, 0x7fffffff);
        while (vis[t]);
}

dijkstra费用流

        鉴于SPFA容易被卡，我们有必要了解一下dijkstra版本的EK费用流。但是现在有一个问题：边权可能是负的（指反边费用），dijkstra不支持带负边权的最短路，如何解决？
        现在需要一种机制消去负边，以满足dijkstra的要求。
        我们考虑给每一个点一个“势”，用数组$h[x]$存起来，在求边权时，计入两个点对应的势。对于$u->v$的一条有向边，我们这样计算它的边权：

        （这里$w$是边的实际边权）然后可以得到含势的最短路不等式：

        为了让计算时边权非负，当然要满足$w+h[u]-h[v]\geq 0$。
        如果势是可以求出的，那么就可以用dijkstra求从源点到汇点的最短路，假设这一条最短路是$S->V_1->V_2->\cdots->T$，那么求出的最短路径长度是：

        无论最短路是什么形式，最终求出的结果就是实际结果加上$h_S-h_T$，减去这个值就可以得到实际的最短路。那么现在如何求这个势？
        当费用都保证非负时，一开始增广一定沿着原边，不可能出现负数边权的情况，于是第一次的增广不用加入势，直接跑一遍dijkstra即可，当然也可以理解成起初势都为0。对于费用为负的情况，在此之前先跑一遍SPFA就好，然后以最短路径dis作为点的势，这里的SPFA只需要跑一遍，不会成为性能瓶颈（如果因为这一遍SPFA卡T了，那么八成是图建的不好）。
        但是从第二次开始，就可能沿反边增广，出现负边权。每一次增广结束时，我们累加每一次的$dis[i]$进入$h[i]$，来得到下一次增广的势，这样做是正确的，可以证明它可以保证$w+h[u]-h[v]\geq 0$。
        简单证明如下，考虑用数学归纳法。
        假设这一次满足：

        那么下一次增广时：

        那么：

        证毕。
        下面给出手写堆+dijkstra+EK的费用流模板题代码：

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
#include <bits/stdc++.h>

#define inf (1<<29)
using namespace std;
struct Edge {
    int next, to, v, p;
} edge[50005 << 1];
int head[5005], n, m, S, T, h[5005], heap[5005], dis[5005], size, ID[5005];
int flow[5005], pre[5005], ans, minCost;

inline void add(int x, int y, int v, int p) {
    static int cnt = 0;
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, edge[cnt].p = p, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, edge[cnt].p = -p, head[y] = cnt++;
}

void down(int x) {
    int x1 = x << 1, x2 = x << 1 | 1, minn = x;
    if (x1 <= size && dis[heap[x1]] < dis[heap[minn]])minn = x1;
    if (x2 <= size && dis[heap[x2]] < dis[heap[minn]])minn = x2;
    if (x != minn)swap(heap[x], heap[minn]), swap(ID[heap[x]], ID[heap[minn]]), down(minn);
}

void up(int x) {
    if (x == 1)return;
    if (dis[heap[x >> 1]] > dis[heap[x]])swap(heap[x >> 1], heap[x]), swap(ID[heap[x >> 1]], ID[heap[x]]), up(x >> 1);
}

inline void add(int x) {
    ID[x] = ++size, heap[size] = x, up(size);
}

inline int top() {
    int t = heap[1];
    ID[heap[1]] = 0;
    if (size != 1)ID[heap[size]] = 1, heap[1] = heap[size--], down(1);
    else size = 0;
    return t;
}

inline int dijkstra() {
    for (int i = 1; i <= n; i++)pre[i] = -1, dis[i] = inf;
    dis[S] = 0, add(S), flow[S] = inf;
    while (size) {
        int f = top();
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && dis[edge[i].to] > dis[f] + edge[i].p + h[f] - h[edge[i].to]) {
                dis[edge[i].to] = dis[f] + edge[i].p + h[f] - h[edge[i].to];//注意这里
                flow[edge[i].to] = min(flow[f], edge[i].v);
                pre[edge[i].to] = i;
                if (ID[edge[i].to])up(ID[edge[i].to]);
                else add(edge[i].to);
            }
        }
    }
    return pre[T] != -1;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &S, &T), memset(head, -1, sizeof(head));
    for (int i = 1, a, b, c, d; i <= m; i++)scanf("%d%d%d%d", &a, &b, &c, &d), add(a, b, c, d);
    while (dijkstra()) {
        int to = T;
        while (to != S)edge[pre[to]].v -= flow[T], edge[pre[to] ^ 1].v += flow[T], to = edge[pre[to] ^ 1].to;
        ans += flow[T], minCost += flow[T] * (dis[T] - h[S] + h[T]);//最后减去势
        for (int i = 1; i <= n; i++)h[i] += dis[i];//势累加
    }
    printf("%d %d", ans, minCost);
    return 0;
}

最大流与二分图匹配

        之前的博客提到了二分图匹配的匈牙利算法，其实这种问题可以用网络流解决。

二分图最大基数匹配

        二分图不带权值，只是单纯的匹配，既可以用网络流也可以用匈牙利算法解决。对于二分图的两个点集A、B，我们建立起点在A中，终点在B中的有向边，权值均为1（这里相当于改造原二分图）；再建立一个源点s，指向所有A中的点，权值为1，建立汇点t，所有B中的点都指向t，权值也为1。在这个图上求得的最大流就是最大匹配数。

二分图最大权完美匹配

        二分图带权值，需要找到权值和最大的匹配方案，完美匹配是指所有点都需要被匹配进去，这时匈牙利算法便不再适用了。这种问题可以用费用流解决：将原图的费用设置成权值的相反数，其余我们自己加的边费用设为0，求最小费用最大流即可。显然最小费用的相反数就是最大权值。如果从源点s出发的点不是全部满载，则完美匹配不存在，否则原图中流量为1的边为最佳匹配边。

二分图最大权匹配

        不要求完美匹配时（即对匹配数不要求）也可以用费用流解决。引入一个新结点P，所有A集合上的点增加一条指向P的边，容量为1，费用为0，同时P引一条边指向汇点t，容量无穷大，费用为0。建完图后求最小费用最大流。这样最大流一定是A中点的个数，但我们给了每个点一个不走B集合点的机会（即从P流向t），这样就得到了最大权。原图中流量为1的边为最佳匹配边。

        以下是网络流模型的较高级部分。

可行流

        对于一条边，在其流量限制的基础上，我们加上一个最小流限制。称最小的经过流量为下界，最大的流量为上界。在这里，记边$e$的上下界分别为$up(e)$与$down(e)$。
        这样，容量限制可以表示成边$e$的实际经过流量$f(x)$满足：

        紧接着考虑点的流量平衡。对于点$x$，我们称其流入流量为$in(x)$，流出流量为$out(x)$，那么流量平衡可以表示为：

        现在，假设我们得到了一张图，它的边上有上下界流量限制，如果存在一种流量配置，即满足流量限制，且所有点满足流量平衡，那么称这一种流量配置为一个可行流。这一种网络流模型中不存在源点和汇点，称为无源汇可行流。
        无源汇可行流中没有源点汇点，流量是凭空产生的，不容易解决。事实上，有一种方法可以将无源汇可行流转化为朴素的最大流问题。
        首先将所有的边的最大限制变成$up(e)-down(e)$，这样最小限制就是$0$，于是转化为普通的最大流问题，但是这样明显是不对的，因为它可能不满足流量平衡性质。考虑转化后的点$x$的实际流量$in(x)-out(x)=0$，但是实际上的流量为$in(x)+out(x)+\sum indown(x)-\sum outdown(x)$。这里的$\sum indown(x)$是指向$x$的所有边的最小容量限制$down(e)$之和，$outdown(x)$是流出$x$的最小容量限制和。后面的求和式显然不是恒为$0$的，这样$x$的流量平衡就会被打破。
        为了消除这种差异，引入新的源点$S$和汇点$T$，并定义$d(x)=\sum indown(x)-\sum outdown(x)$。这样对于所有的点，添加新边：

  • 若$d(x)>0$，则建立$S$指向$x$，最大流量限制为$d(x)$的边。
  • 若$d(x)<0$，则建立$x$指向$T$，最大流量限制为$-d(x)$的边。
  • $d(x)=0$时忽略。

        容易发现，在引入这些边后，我们从外界引入流量消除了因最小容量限制和带来的差异，若此时存在一种流量配置可以使$S$到$T$满流，那么对于除了源点和汇点的每一个点，必然都满足流量平衡条件。若此时不满流，则可行流不存在。这样就得到了一种将无源汇可行流问题转化为最大流的正确算法。
        模板SGU194。

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
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
struct Edge
{
    int next, to, v;
} edge[100005];
int cnt, d[205], n, m, head[205], s, t, dep[205], ans, H, low[100005];
queue<int> que;
inline void add(int x, int y, int v)
{
    edge[cnt].next = head[x], edge[cnt].to = y, edge[cnt].v = v, head[x] = cnt++;
    edge[cnt].next = head[y], edge[cnt].to = x, edge[cnt].v = 0, head[y] = cnt++;
}
inline int BFS()
{
    for (int i = s; i <= t; i++) dep[i] = inf;
    que.push(s), dep[s] = 0;
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && dep[edge[i].to] == inf) dep[edge[i].to] = dep[f] + 1, que.push(edge[i].to);
        }
    }
    return dep[t] != inf;
}
int DFS(int x, int limit)
{
    if (x == t || limit == 0) return limit;
    int f, flow = 0;
    for (int i = head[x]; ~i; i = edge[i].next) {
        if (dep[edge[i].to] == dep[x] + 1 && (f = DFS(edge[i].to, min(edge[i].v, limit)))) {
            edge[i].v -= f, edge[i ^ 1].v += f, limit -= f, flow += f;
            if (limit == 0) break;
        }
    }
    return flow;
}
int main()
{
    memset(head, -1, sizeof(head)), scanf("%d%d", &n, &m), s = 0, t = n + 1;
    for (int i = 1, a, b, l, r; i <= m; i++) {
        scanf("%d%d%d%d", &a, &b, &l, &r), add(a, b, r - l), d[b] += l, d[a] -= l, low[i] = l;
    }
    for (int i = 1; i <= n; i++) {
        if (d[i] > 0) add(s, i, d[i]), H += d[i];
        if (d[i] < 0) add(i, t, -d[i]);
    }
    while (BFS()) ans += DFS(s, inf);
    if (ans == H) {
        printf("YES\n");
        for (int i = 0; i < m; i++) {
            printf("%d\n", edge[(i << 1) ^ 1].v + low[i + 1]);
        }
    } else {
        printf("NO");
    }
    // PAUSE;
    return 0;
}

        现在考虑有源汇可行流。有源点和汇点的区别就是源点和汇点可以不满足流量平衡条件。我们可以从汇点引一条边指向汇点，下界为$0$，上界无穷大，这样平衡掉源汇点，就可以转化为无源汇的可行流问题。
        可行流也有费用流问题，是求在可行流的基础上的最小费用问题。只需要将求最大流的过程改为最小费用最大流即可。

上下界有源汇网络流

        先考虑有上下界的有源汇最大流。
        要拥有最大流需要先有可行流，首先应该先求原图的可行流，在可行流存在的情况下再求解最大流。
        接下来，我们撤掉因求可行流而引入的超级源点和超级汇点，而不撤掉从汇点引向源点的额外边。
        这个过程可以这样解释：对于流入汇点的净流量，记为$f$，额外边引走的流量记为$p$，下界流和记为$d(T)$，那么：

        紧接着，我们从$S$开始到$T$求最大流，进行增广过程，这样实际的最大流值为$f+\Delta f+d(T)$，也就是$p+\Delta f$。$p$这一段流量可以通过反向边获得，之后加上再获得的额外流就是实际的最大流。
        当然，我们也可以撤掉额外边，此时答案就需要在最后的答案上手动加上$p$。为了与最小流对应，这种方法其实更推荐。
        这样需要注意的一个问题是，在剥离超级源点汇点以及额外的边后，剩余的图其实并不是流量平衡的（其实这种非平衡的状态是我们有意设置的）。求最大流的过程不会对这种非平衡的状态产生影响，保证了算法的正确性。
        模板Loj116。

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
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
struct Edge {
    int next, to, v;
} edge[100005];
int cnt, d[205], n, m, head[205], s, t, dep[205], ans, H, ss, tt;
queue<int> que;
inline void add(int x, int y, int v) {
    edge[cnt].next = head[x], edge[cnt].to = y, edge[cnt].v = v, head[x] = cnt++;
    edge[cnt].next = head[y], edge[cnt].to = x, edge[cnt].v = 0, head[y] = cnt++;
}
inline int BFS() {
    for (int i = 0; i <= n + 1; i++) dep[i] = inf;
    que.push(s), dep[s] = 0;
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && dep[edge[i].to] == inf)
                dep[edge[i].to] = dep[f] + 1, que.push(edge[i].to);
        }
    }
    return dep[t] != inf;
}
int DFS(int x, int limit) {
    if (x == t || limit == 0)
        return limit;
    int f, flow = 0;
    for (int i = head[x]; ~i; i = edge[i].next) {
        if (dep[edge[i].to] == dep[x] + 1 && (f = DFS(edge[i].to, min(edge[i].v, limit)))) {
            edge[i].v -= f, edge[i ^ 1].v += f, limit -= f, flow += f;
            if (limit == 0)
                break;
        }
    }
    return flow;
}
int main() {
    memset(head, -1, sizeof(head)), scanf("%d%d%d%d", &n, &m, &ss, &tt), s = 0, t = n + 1;
    for (int i = 1, a, b, l, r; i <= m; i++) {
        scanf("%d%d%d%d", &a, &b, &l, &r), add(a, b, r - l), d[b] += l, d[a] -= l;
    }
    add(tt, ss, inf);
    for (int i = 1; i <= n; i++) {
        if (d[i] > 0)
            add(s, i, d[i]), H += d[i];
        if (d[i] < 0)
            add(i, t, -d[i]);
    }
    while (BFS()) ans += DFS(s, inf);
    if (ans == H) {
        for (int i = head[s]; ~i; i = edge[i].next) edge[i].v = edge[i ^ 1].v = 0;//撤掉超级源点
        for (int i = head[t]; ~i; i = edge[i].next) edge[i].v = edge[i ^ 1].v = 0;//撤掉超级汇点
        s = ss, t = tt, ans = 0;//不撤额外边
        while (BFS()) ans += DFS(s, inf);
        printf("%d", ans);
    } else {
        printf("please go home to sleep");
    }
    // PAUSE;
    return 0;
}

        另一个问题是最小流。它和求最大流类似。撤掉超级源点汇点和额外边，从汇点$T$开始跑最大流，逆向回流，将多余可以空出的流量流回，就可以得到最小流。初始的流量就是额外边中的流量。
        模板：Loj117。
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
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
struct Edge {
    int next, to, v;
} edge[500005];
int cnt, d[60000], n, m, head[60000], s, t, dep[60000], ans, H, ss, tt, ed;
int cur[60000];
queue<int> que;
inline void add(int x, int y, int v) {
    edge[cnt].next = head[x], edge[cnt].to = y, edge[cnt].v = v, head[x] = cnt++;
    edge[cnt].next = head[y], edge[cnt].to = x, edge[cnt].v = 0, head[y] = cnt++;
}
inline int BFS() {
    for (int i = 0; i <= n + 1; i++) dep[i] = inf, cur[i] = head[i];
    que.push(s), dep[s] = 0;
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && dep[edge[i].to] == inf)
                dep[edge[i].to] = dep[f] + 1, que.push(edge[i].to);
        }
    }
    return dep[t] != inf;
}
int DFS(int x, int limit) {
    if (x == t || limit == 0)
        return limit;
    int f, flow = 0;
    for (int i = cur[x]; ~i; i = edge[i].next) {
        cur[x] = i;
        if (dep[edge[i].to] == dep[x] + 1 && (f = DFS(edge[i].to, min(edge[i].v, limit)))) {
            edge[i].v -= f, edge[i ^ 1].v += f, limit -= f, flow += f;
            if (limit == 0)
                break;
        }
    }
    return flow;
}
int main() {
    memset(head, -1, sizeof(head)), scanf("%d%d%d%d", &n, &m, &ss, &tt), s = 0, t = n + 1;
    for (int i = 1, a, b, l, r; i <= m; i++) {
        scanf("%d%d%d%d", &a, &b, &l, &r), add(a, b, r - l), d[b] += l, d[a] -= l;
    }
    ed = cnt, add(tt, ss, inf);
    for (int i = 1; i <= n; i++) {
        if (d[i] > 0)
            add(s, i, d[i]), H += d[i];
        if (d[i] < 0)
            add(i, t, -d[i]);
    }
    while (BFS()) ans += DFS(s, inf);
    if (ans == H) {
        for (int i = head[s]; ~i; i = edge[i].next) edge[i].v = edge[i ^ 1].v = 0;
        for (int i = head[t]; ~i; i = edge[i].next) edge[i].v = edge[i ^ 1].v = 0;
        s = tt, t = ss, ans = edge[ed ^ 1].v, edge[ed].v = edge[ed ^ 1].v = 0;//撤掉额外边
        while (BFS()) ans -= DFS(s, inf);
        printf("%d", ans);
    } else {
        printf("please go home to sleep");
    }
    // PAUSE;
    return 0;
}