网络流

naoliaok_lovely · 2023-11-21 18:49:35 · 算法·理论

ps.：由于篇幅限制，本篇文章很多地方没有放图，太占空间，文章涉及到“自行推导”的字眼一般都是很显然的，读者如果不能一眼还是建议手推一下。

一、基本模型与概念

1.网络流模型

网络流模型是指一个边带权值且连通的有向图，并且该图中只存在一个入度为 0 的点（源点 S）和 一个出度为 0 的点（汇点 T）。

2.概念

基本概念：

• 容量(Capacity)：c(u,v) 表示 u\to v 这条有向边的最大流量。
• 流量(Flow)：f(u,v) 表示 u\to v 这条有向边的实际流量。
• 残量：每条边的容量与流量之差。

注：本文用 u\xrightarrow cv 表示连了一条容量为 c 的 x\to y 的有向边。

性质：

1. 容量限制：f(u,v)\le c(u,v)。
2. 流量守恒：对于所有点（除了源点和汇点），流入的流量 = 流去的流量。
3. 斜对称性：f(u,v)=-f(v,u)。

建图处理：将有向图变为无向图（没有的边容量为 0）。 事实上，在代码中我们不会去刻意区分 c 和 f，只需要用残量代替即可。
ps.：鉴于我们会处理反向边，每条边与他的反向边一定要连续。

update20231207：为了建边时更加方便（也更加方便调试），建议采用如下的写法建边。本文中有一些代码是以前写的，这里就不做修改了。

int h[N], ne[M], e[M], w[M], idx = 1;
void add(int a, int b, int c)
{
    e[++idx] = b, w[idx] = c, w1[idx] = d, ne[idx] = h[a], h[a] = idx;
}
void add1(int a, int b, int c)
{
    add(a, b, c), add(b, a, 0);
}

二、最大流

• 路：一个元素不重复的序列，表示从源点到汇点的一条路径，相邻点必须存在有向边连接。
• 增广路：对于一条路，如果每条边的残量都大于 0，则称这条路为增广路。

定理：如果残留网络存在增广路，则流量可以增大。
逆定理：如果残留网络不存在增广路，则当前流量是最大流量。

P3376 【模板】网络最大流
下面将以各种算法在本题的实现进行举例。

在讲解之前，先给出各算法的效率对比。（摘自这篇博客）

（虽然但是，怎么 EK 和 ISAP 一样快啊喂！！！）

1.FF(Ford-Fulkerson) 算法

对增广路进行深搜，直到不存在增广路。每次找到一条增广路后，我们都沿着这条路走一遍。设这条路的最小残量为 w，那么相当于这条路上的每条边都要流过 w 的水，故将残量减去 w。为了保证“斜对称性”，我们让每条边的反向边的残量加上 w。（建议仔细思考算法的正确性）

时间复杂度：O(nm^2)。
由于效率奇高无比，这里就不给代码了，与下面 EK 相似。

2.EK(Edmonds-Karp) 算法

对增广路进行宽搜，直到不存在增广路。

时间复杂度：O(nm^2)。

#include<bits/stdc++.h>
using namespace std;
#define LL long long

const int N = 210;
int n, m, S, T;
LL d[N][N], ans;

LL flow[N];
int pre[N];//记录路径
int q[N], hh, tt;
bool EK()
{
    memset(flow, 0, sizeof(flow));
    flow[q[hh = tt = 1] = S] = 1e18;
    while(hh <= tt)
    {
        int t = q[hh++];
        if(t == T) return true;
        for(int i = 1; i <= n; i++)
            if(d[t][i] && !flow[i])
                flow[q[++tt] = i] = min(flow[t], d[t][i]), pre[i] = t;
    }
    return false;
}

int main()
{
    cin >> n >> m >> S >> T;
    for(int i = 1, a, b, c; i <= m; i++)
        cin >> a >> b >> c, d[a][b] += c;

    while(EK())
    {
        ans += flow[T];
        for(int i = T; i != S; i = pre[i])
            d[pre[i]][i] -= flow[T], d[i][pre[i]] += flow[T];
    }
    cout << ans << endl;
    return 0;
}

链式前向星版：

#include<bits/stdc++.h>
using namespace std;
#define LL long long

const int N = 210, M = 10010;
int n, m, S, T;
LL ans; 

int h[N], ne[M], e[M], w[M], idx = 1;
void add(int a, int b, int c)
{
    e[++idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}

LL flow[N];
int pre[N];//记录路径
int q[N], hh, tt;
bool EK()
{
    memset(flow, 0, sizeof(flow));
    flow[q[hh = tt = 1] = S] = 1e18;
    while(hh <= tt)
    {
        int t = q[hh++];
        if(t == T) return true;
        for(int i = h[t]; i; i = ne[i])
            if(w[i] && !flow[e[i]])
                flow[q[++tt] = e[i]] = min(flow[t], (LL)w[i]), pre[e[i]] = i;
    }
    return false;
}

int main()
{
    cin >> n >> m >> S >> T;
    for(int i = 1, a, b, c; i <= m; i++)
        cin >> a >> b >> c, add(a, b, c), add(b, a, 0);

    while(EK())
    {
        ans += flow[T];
        for(int i = T; i != S; i = e[pre[i] ^ 1])
            w[pre[i]] -= flow[T], w[pre[i] ^ 1] += flow[T];
    }
    cout << ans << endl;
    return 0;
}

3.(I)SAP((Improved) Shortest Augmenting Paths) 算法

注意到，我们在上面搜的过程中，每次搜到一条增广路，就要从头开始。这十分冗余，考虑仅仅回退一步。实现的时候，可以记录 dis 数组表示每个点到汇点的距离。对于 i 号点，当且仅当他所连接的 j 满足 dis_i=dis_j+1 的时候，我们才会去搜 j。一旦当前点流入后无法流出，我们就让当前点的 dis+1。通过这样的方式，实现了一个类似于分层图的操作。一种形象的理解是，dis 表示这个点后面还要经过几个点。一旦走不动了，说明需要绕路，增加距离即可。显然，中止状态有两个：

在实现的时候，我们不需要单独去处理 dis 数组的初始化，直接在函数进行的时候通过自增的方式初始化即可。

时间复杂度：O(n^2m)。

#include<bits/stdc++.h>
using namespace std;
#define LL long long 

const int N = 210;
int n, m, s, t;
LL d[N][N], ans; 

int dis[N], cnt[N];//这两个数组要注意多测清空
LL sap(int x, LL inflow)
{
    if(x == t) return inflow;
    LL outflow = 0;
    for(int i = 1; i <= n; i++)
        if(d[x][i] && dis[x] == dis[i] + 1)
        {
            LL flow = sap(i, min(inflow - outflow, d[x][i]));
            d[x][i] -= flow, d[i][x] += flow, outflow += flow;
            if(inflow == outflow || dis[s] >= n) return outflow; 
        }
    if(!--cnt[dis[x]]) dis[s] = n;
    cnt[++dis[x]]++;
    return outflow;
}

int main()
{
    cin >> n >> m >> s >> t;
    for(int i = 1, a, b, c; i <= m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] += c;
    }

    while(dis[s] < n) ans += sap(s, 1e18);//一般来说，这个最大 dis 取总点数

    cout << ans << endl;
    return 0;
}

链式前向星版：（埋下伏笔）

#include<bits/stdc++.h>
using namespace std;
#define LL long long 

const int N = 210, M = 10010;
int n, m, s, t;
LL ans; 

int h[N], ne[M], e[M], w[M], idx = 1;
void add(int a, int b, int c)
{
    e[++idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}

int dis[N], cnt[N];
LL sap(int x, LL inflow)
{
    if(x == t) return inflow;
    LL outflow = 0;
    for(int i = h[x]; i; i = ne[i])
        if(w[i] && dis[x] == dis[e[i]] + 1)
        {
            LL flow = sap(e[i], min(inflow - outflow, (LL)w[i]));
            w[i] -= flow, w[i ^ 1] += flow, outflow += flow;
            if(inflow == outflow || dis[s] >= n) return outflow; 
        }
    if(!--cnt[dis[x]]) dis[s] = n;
    cnt[++dis[x]]++;
    return outflow;
}

int main()
{
    cin >> n >> m >> s >> t;
    for(int i = 1, a, b, c; i <= m; i++)
        scanf("%d%d%d", &a, &b, &c), add(a, b, c), add(b, a, 0);

    while(dis[s] < n) ans += sap(s, 1e18);

    cout << ans << endl;
    return 0;
}

而前面的“improved”，增加了一个当前弧优化：注意到，对于菊花图，上面代码的运行效率可能稍差。我们可以增加一个标记 cur 表示当前讨论到的边（即 h'），这样就无需遍历全部的链式前向星。在 dis 增加的时候，要把对应的 cur 回到 h。

#include<bits/stdc++.h>
using namespace std;
#define LL long long 

const int N = 210, M = 10010;
int n, m, s, t;
LL ans; 

int h[N], ne[M], e[M], w[M], idx = 1;
void add(int a, int b, int c)
{
    e[++idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}

int dis[N], cnt[N], cur[N];
LL sap(int x, LL inflow)
{
    if(x == t) return inflow;
    LL outflow = 0;
    for(int &i = cur[x]; i; i = ne[i])
        if(w[i] && dis[x] == dis[e[i]] + 1)
        {
            LL flow = sap(e[i], min(inflow - outflow, (LL)w[i]));
            w[i] -= flow, w[i ^ 1] += flow, outflow += flow;
            if(inflow == outflow || dis[s] >= n) return outflow; 
        }
    if(!--cnt[dis[x]]) dis[s] = n;
    cnt[++dis[x]]++, cur[x] = h[x];
    return outflow;
}

int main()
{
    cin >> n >> m >> s >> t;
    for(int i = 1, a, b, c; i <= m; i++)
        scanf("%d%d%d", &a, &b, &c), add(a, b, c), add(b, a, 0);

    for(int i = 1; i <= n; i++) cur[i] = h[i];
    while(dis[s] < n) ans += sap(s, 1e18);

    cout << ans << endl;
    return 0;
}

4.Dinic 算法

与上面的 SAP 类似，将 dis 改为每个点到源点的距离即可。

时间复杂度：O(n^2m)。
从上面的表可以看出，大多数情况其实都不如 ISAP，所以平时还是用 ISAP 吧。

5.HLPP(Highest Label Preflow Push) 算法

全称叫“最高标号预流推进算法”，简称“预流推进”算法，相对上面的几种更复杂，但是也更快。一般情况下，ISAP 就够用了，当然也不乏会有缺德的出题人……

现在还没遇到，可以去 P4722 【模板】最大流 加强版 / 预流推进 自学。

时间复杂度：O(n^2\sqrt m)。

6.建图技巧

网络流的题目，难就难在建图上。这里整理了常见的建图技巧。

• 拆点：我们知道，网络流中唯一的限制条件是容量，而他只能限制边上的最大流量。那如何限制点上的最大容量呢？这个时候可以使用拆点的方式，把同一个点拆成两个，并连上单向边 u\to v，c(u,v) 就是限制的点的最大容量。
• 虚点：我们常常需要通过创建虚点的方式来辅助建图，最经典的是虚拟源点和虚拟汇点。
• 矩阵模型：有一大类题是在给定的矩阵上建图。这时一般有两种建图方式：给每一个点编号并暴力连边；把每行、每列视作一个点，再互相连边。
• 分层图模型：对于明显的分层图，一种提高效率的方式是直接在残留网络上继续增广。每次增广前先将 dis 数组暴力清空。复杂度稍加思考可以发现，如果层数多则每层的点少；每层的点多则层数少。这使得我们增广路的长度是可以保证的。（直接跑即可）

7.例题

基础运用：

P2472 [SCOI2007] 蜥蜴
需要先转化题意，再套用最大流。

P1402 酒店之王
拆点的经典运用。

NKOJ3517 宝藏
表面上一看是一道上下界，但是发现题目的特殊性质，稍加转化即可。用到了上面说的将每行每列看做一个点的技巧。

进阶运用：

P3163 [CQOI2014] 危桥
不再那么模板，需要一些巧妙的转化。首先将“往返”转化成“前往”，次数 \times2 即可。至于对应源点到对应汇点的限制，则通过交换源汇点的方式处理。
具体的，对于普通的桥，用并查集直接处理；对于危桥，建出对应的图，然后跑 a1,b1 为源点，a2,b2 为汇点的网络流，如果不行，不然无解；否则交换 b1,b2，再跑一遍即可。

三、最小割

1.概念与定理

• 割：是网络中的一个划分，将所有点划分为 S 和 T 两个点集，记为 Cut(S,T)。其中，源点 s\in S，汇点 t\in T。对于点 i，若 s 可以到达 i，则 i\in S；若 i 可以到达 t，则 i\in T。
• 割边：对于边 u\to v 满足 u,v 两个端点属于不同的集合。
• 正向割边：u\in S,t\in T。
• 逆向割边：u\in T,t\in S。
• 割的容量：所有正向割边的容量总和。

定理一：如果 f 是网络的一个流，Cut(S,T) 是任意一个割，则 f 等于正向割边的流量与反向割边的流量之差。
推论一：如果 f 是网络的一个流，Cut(S,T) 是一个割，那么 f 的值不超过割 Cut(S,T) 的容量。
推论二：网络中的最大流不超过任何割的容量。
定理二：如果 f 是网络的一个流，Cut(S,T) 是一个割，且 f 的值等于 Cut(S,T) 的容量，那么 f 为最大流。
定理三：在任意网络中，最大流的值等于最小割的容量。
推论：在任意网络中，设 Cut(S,T) 是一组最小割，则所有的正向割边的流量均为容量，逆向割边的流量均为 0。

关于最小割为什么不能随意的连双向边的讨论

之前的最大流对于大部分的边连双向边都是没有问题的。（当然可能有例外）但是对于最小割情况就反过来了：大部分的边如果盲目的连成了双向边会导致答案错误。这使得很多初学者感到不解，这里记录下自己的见解，若有不当欢迎指出。
我们做最小割的题目是由于“最小割等于最大流”这个定理成立，从而转化成最大流处理的。但是请注意，这里的“最小割”是指的“正向割边的容量总和”。但是如果连反向边，很有可能导致一些反向割边错误的计算进了答案。所以，只有在保证多连的那条边一定不会被割掉或者一定是反向割边时，才能加入。
然而对于大部分的图，那些节点有可能属于 S，也有可能属于 T，这时的反向边自然错误。

2.寻找最小割上的边

【法一】：先求出最大流 maxf，暴力枚举每一条边，如果断掉这条边之后的最大流 maxf' 满足 manf'+c=maxf，则当前这条边在最小割上。更新 maxf，然后彻底断掉这条边。直到 maxf=0 为止。（过于暴力！但是可以解决有要求的题目，比如字典序限制等）
【法二】：在残量网络中，通过 bfs 直接求得 S 和 T。（残量为 0 的边视作断开）对于那些端点属于不同集合的边，即为最小割上的边。
（拓展）直接在残留网络上跑，可能会存在点不属于任何集合。这代表着最小割的方案不唯一，将这个点归入任意集合都是一种方案。（当然两个集合得各自连通）

3.例题

基础运用：

P1344 [USACO4.4] 追查坏牛奶 Pollutant Control
先看第一问，题目要求最小割，直接跑最大流即可。
第二问比较经典，求的是边数最少的最小割。处理方式是，先将题目的边权改为 c_i\gets1001c_i+1，再跑最大流。最后算出来的最大流就是 \lfloor\frac {maxf}{1001}\rfloor，边数就是 maxf\bmod1001。（因为最多 1000 条边）
第三问洛谷上被删掉了，NKOJ1852 [USACO4.4.2]Pollutant Control追查坏牛奶，问的是给出第二问中字典序最小的方案。这时就要用到上面的法一了，虽然粗暴，但也最实用。

染色模型：

P3756 [CQOI2017] 老C的方块
据说是巨佬 nodgd 出的，不愧为网络流神题，也算是正式踏入网络流的必做之题。这里不想以很简单的几句话就将这道好题敷衍过去，但是要想说清楚要占用很大的篇幅，故请读者自行阅读题解。

P1935 [国家集训队] 圈地计划
相比于上面那道简单一点，但是做出了上面那道不代表一定可以做出这道。
看到“相邻边”，很容易想到通过“割”的方式处理。将原题的“最大收益”转化为“最小亏损”（先获得所有收益），把那些亏损都体现在图上。这样一说感觉像一道水题，真正写起来就发现问题了：
每个点显然都会先向源点、汇点连边权为 a,b 的边，这没有问题。接着将这些点相连，代表相邻关系。但是仔细一想，这一部分的边权似乎应该为 -c？？？然后就可以开始罚坐哩~~~
事实上，由于整张图为二分图，仍然进行染色处理。然后，我们强行令黑色方格的类型反转。这样做就可以让上面的 -c 变成 +c 了。

链式模型：

P3227 [HNOI2013] 切糕
一道经典的链式建图题目。每个点都有若干个高度可以选，于是我们把这些高度拉成一条链，把点权放到边上，用切断边来表示这个点选择了这个高度。

NKOJ8314 tower
这题相信很快可以看出“链”在哪里——每座炮塔能够攻击到的所有格子形成了一条链。问题在于如何控制“路径不相交”这个恶心条件。这里要用到一个技巧“反链”，即把链反着连。操作如下：
首先考虑所有炮塔连接源点。手搓一下发现，似乎倒着连可以解决问题？于是把所有炮塔连接汇点，发现还是差一些信息。事实上，我们把所有横着的链正着连，竖着的链反着连。这样做的好处在于，一旦出现相交，那么 -3,-4 的炮塔一定可以到达 -1,-2 的炮塔。于是，我们把 -1,-2 的炮塔连汇点，-3,-4 的炮塔连源点即可。

倍增/树剖建图：

CF768E ALT
这道题的暴力应该挺简单的，把人看做 A 类点，边看做 B 类点，用上面说的割掉一条边来表示选择。展现到图上就变成了 A 类的每一个点与他覆盖的每一条边所对应的点连边，边权为无穷大即可。
但是这样的边数是 O(nm) 的，瓶颈在于上面那些表示覆盖的边。注意到这时我们不用暴力连边，通过建虚点的方式来减少我们的边数即可。

综合应用：

P3511 [POI2010] MOS-Bridges
做了这道题之后发现最小割的建图似乎确实比普通的最大流难一点？（考法灵活了很多
首先回忆有向图欧拉回路的充要条件：

1. 除去所有孤立点（没有连边的点），整张图连通（无向图意义下）；

分析题目，一眼二分答案。条件一很好检验，条件二就比较棘手了。题目的意思是，每条边只能走一次，也就是说我们要给无向边定向。祭出我们常见套路，先随便给他定一个向，考虑改变这条边方向带来的影响。最简单的，假设此时的方向就是正确答案，考虑如何验证：连边 s\xrightarrow{in}i,i\xrightarrow{out}t，判断 maxf=\sum in 即可。
在草稿纸上稍加推导可以发现，对于那些双向边，为了进行反向操作，我们可以连一条 i\xrightarrow{2}j 的边。注意到，如果 f(i,j)=0，意味着这条边不反向；f(i,j)=2 则反向。但是 f(i,j)=1 是不合法的，我们不希望他出现！
接下来的转化极为巧妙：直接将图上的所有容量 \div2！这一步看起来荒谬至极，但仔细思考，正确性不难证明。我们上面的 i\xrightarrow{2}j 的边，显然是不会改变奇偶性的（只会流 0,2 嘛，1 不合法）。所以，对于一个点，如果他的 in_i,out_i 奇偶性不同，显然无解；否则如果同为奇数，那肯定会有 f(s,i,t)\ge1，我们让 c(s,i)-1,c(i,t)-1。经过了上面的操作，连接源点汇点的边权也都变成了偶数，这时给他暴力 \div2，就可以避免之前说的 f(i,j)=1 的问题。

NKOJ8316 买酒卖酒
检验是否学懂了最小割的题目:)
首先对于 30\%，直接暴力建图跑最大流即可。边数是 O(n^2) 级别的，仔细思考，发现其实没有什么优化建图技巧可以使用的。
那怎么办呢？相信此时会有这样的疑惑：这道题明明是最大流，和最小割什么关系？

事实上，这道题需要走出一个误区：我们都知道等式是双向的。我们以前解题都在用最大流求最小割，可曾想过其实可以用最小割解决最大流问题呢？
问题转化为求最小割，这其实就是所谓的“模拟最大流”。由于这张图很特殊，求最小割其实是可以做到 O(n^2) 解决的——没错，动态规划！设状态 f_{i,j} 表示当前讨论到前 i 个点，有 j 个点属于 S 集合的最小代价。转移式也很简单，f_{i,j}=\min(f_{i-1,j}+jm+a_i,f_{i-1,j-1}+b_i)。

事实上，这个方法也可以称为模拟最小割。

4.对偶图最短路

• 平面图：如果图 G 能画在平面 S 上，即除顶点外无边相交，则称 G 可平面嵌入 S，G 为可平面图或平面图。画出的没有边相交的图称为 G 的平面表示或平面嵌入。
• 对偶图：设 G 是平面图的某一个平面嵌入，构造图 G'：
  1. 在 G 的每个面 R_i 中放置 G' 的一个顶点 v_i'。
  2. 设 e 为 G 的一条边，若 e 在 G 的面 R_i 和 R_j 的公共边界上，做 G' 的边 e' 与 e 相交，且 e' 连接 G' 的顶点 v_i',v_j'，即 e'=(v_i', v_j')，e' 不与其他任何 G' 中的边相交。若 e 为 G 中的桥且在 R_i 的边界上，则 e' 是连接 R_i 的顶点 v_i' 的自环，即 e'=(v_i',v_i')。

——摘自 OI-wiki，做了部分描述上的修改。

既然叫对偶图，显然是两两成对的。容易证明，对偶图的对偶图为原图。

更多的内容感兴趣可以自行了解，但是在 OI 中，记住结论就行了：
原图的最小割与对偶图的最短路相等。
证明略。

解释：此处的“最小割”大家都懂，但是“最短路”指的是什么？源点和汇点是什么呢？
设原图的源点为 s，汇点为 t，我们连接 s,t（不与其它边相交，即仍然要保证是一个平面图）。于是，原本整张图的外面构成一个面 R_1，就被我们分割为了 R' 和 R''。接下来按照之前的方式建对偶图，不过不把 R' 和 R'' 相连，即我们额外连接的那条 (s,t) 的边不进行上面的建边处理。最后，求出 R' 和 R'' 的最短路即可。

这有什么作用呢？我们知道，最大流算法的复杂度是比较高的，其实很多“正常”的数据范围都跑不了。例如下面的例题，显然都可以用最大流算法写，但是无法通过。而改用最短路算法可以做到 O(n\log n)。

P4001 [ICPC-Beijing 2006] 狼抓兔子
事实上，如何建对偶图，这是一个不简单的工作。目前用的比较多的叫最小左转法，但是也不简洁。所以在 OI 中，大多数对偶图的题目都是方格状的，像此题一样。
按照上述说的，建出对偶图，跑 dijkstra 即可。（为啥不用 spfa？呵呵）

习题：P2046 [NOI2010] 海拔，P7916 [CSP-S 2021] 交通规划。

四、最大权闭合子图

• 闭合子图：一个有向图中，选取一些点构成点集 V，如果 V 中任意点的出边所指向的点也在 V 中，则我们称 V 为闭合子图。
• 最大权闭合子图：即点权总和最大的闭合子图。（显然，从上面的定义可以发现，只有对于一个带点权的有向图才有这一说。特点：点权可以为负！）

方法：

1. 对于 w_i\ge0，连边 s\xrightarrow{w_i}i；对于 w_i\le0，连边 i\xrightarrow{-w_i}t。
2. 如果在原图中存在边 i\to j，则连边 i\xrightarrow{+\infty}j。
3. 答案为正点权之和 - 最大流，即 ans=\sum\limits_{w_i\ge0}w_i-maxf。

给出一个不算特别严谨，但是容易理解的证明：

引理：对于图上的任意一个割 Cut(S,T)，S 一定是一个闭合子图。

考虑反证，如果不是闭合子图，则一定存在点对 (i,j) 使得存在 i\to j 的边且 i\in S，j\in T。此时，因为我们连了边权为 +\infty 的边，那条边一定没有被割掉，所以 s\to\dots\to i\to j\to\dots\to T 构成了一条路径，与割 Cut(S,T) 矛盾。

考虑怎么把这个子图的权值表示出来？ 考虑割边的实际意义：对于 $s$ 出发的所有割边，代表着我们不选这个正权点；对于 $t$ 结束的所有割边，代表我们选择了这个负权点。 所以上面的公式 $\sum\limits_{w_i\ge0}w_i-cutc$ 就代表了这个方案的权值和，其中 $cutc$ 表示割的容量。 又因为 $cutc=maxf$，故命题得证。

1.例题

基础运用：

太空飞行计划问题
模板题，把 E 看做正权点，I 看做负权点。将题目的包含关系对应的图建出来，则变为了上面所述模型。

P3749 [六省联考 2017] 寿司餐厅
非常经典的一道题，但是没有什么技巧，所以也不能算的太难。显然那些 d_{i,j} 是有偏序关系的，很快可以建出来表示正权的那些点。注意连边的时候不需要把所有有包含关系的区间都连边，只需要连 [i,j]\to[i,j-1] 和 [i,j]\to[i+1,j] 就好了。
观察负权值的计算公式 mx^2+cx，前面的 mx^2 启示我们无论多少，只要有一个这个代号的寿司就会付钱，所以对于每一个代号建一个虚点，点权为 -mx^2 即可。后面的 cx 就很简单了，对于寿司 d_{i,i} 赋权值 -x 即可。

进阶运用：

CF103E Buying Sets
其实从最大权闭合子图的角度讲不难，但是第一步的转化很巧妙，所以可能这个题的标签为“思维题”更合适。
突破点肯定在于第一句话：这 n 个子集的并集刚好是 n 个元素，且任意 k 个子集的并集大小 \ge k。显然这是一个二分图（左边表示集合，右边表示元素），进一步的，这句话其实可以翻译为：这个二分图存在完美匹配！（读者自证不难qwq)
于是跑完美匹配，用一个元素代表一个集合，那么选择了这个元素就必须选择这个集合的其他元素。即可对元素建图跑最大权闭合子图。

五、费用流

在最大流的基础上，每条边多了一个费用 w，表示单位时间通过每单位的水需要的费用。
注：本文用 u\xrightarrow[w]cv 表示连了一条容量为 c、费用为 w 的 x\to y 的有向边。

• 最小费用最大流：在最大流的基础上，求最小费用。

1.SSP 算法

本质上是一个基于贪心的算法，过程如下：

1. 求最小费用增广路：用 SPFA 跑最短路即可，如果残量为 0 就不能走，顺便记录一下流量。
2. 将这条路径增广，更新残量。
3. 重复执行，直到不存在增广路。

正确性显然。
ps：相信有人会问，用 spfa 跑最短路，如果有负环怎么办呢？可以证明，如果初始的图中没有负环，则在执行过程中一定不会出现负环。而一旦初始的图中有负环，则需要额外的处理手法，在后文会有提到。

但这玩意看起来就很慢，具体复杂度逛了一圈没找到让我满意的……

设每次找增广路的时间复杂度为 O(nm)，该网络的最大流为 f，则最坏时间复杂度为 O(nmf)。这是一个关于值域的多项式，所以是伪多项式时间的。
可以构造 m=n^2,maxf=2^{\frac n2} 的网络使得 SSP 算法的时间复杂度达到 O(n^32^{\frac n2})，所以 SSP 算法不是多项式时间的。
——摘自 OI-Wiki

P3381 【模板】最小费用最大流
（写起来确实很像 EK）

#include<bits/stdc++.h>
using namespace std;

const int N = 5010, M = 1e5 + 10;
int n, m, s, t, ans1, ans2;

int h[N], ne[M], e[M], w[M], w1[M], idx = 1;
void add(int a, int b, int c, int d)
{
    e[++idx] = b, w[idx] = c, w1[idx] = d, ne[idx] = h[a], h[a] = idx;
}

int flow[N], dis[N], pre[N];
int q[N], hh, tt;
bool in[N];
bool ssp()
{
    memset(flow, 0, sizeof(flow));
    memset(dis, 0x3f, sizeof(dis));
    memset(in, 0, sizeof(in));
    hh = tt = 0;
    flow[s] = INT_MAX, dis[s] = 0, in[q[tt++] = s] = 1;
    while(hh != tt)
    {
        int t = q[hh++]; in[t] = 0;
        if(hh == N) hh = 0;
        for(int i = h[t]; i; i = ne[i])
            if(w[i])
            {
                int j = e[i];
                if(dis[j] > dis[t] + w1[i])
                {
                    flow[j] = min(flow[t], w[i]), dis[j] = dis[t] + w1[i], pre[j] = i;
                    if(!in[j])
                    {
                        in[q[tt++] = j] = 1;
                        if(tt == N) tt = 0;
                    }
                }
            }
    }
    return flow[t];
}

int main()
{
    cin >> n >> m >> s >> t;
    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), add(b, a, 0, -d);

    while(ssp())
    {
        ans1 += flow[t], ans2 += flow[t] * dis[t];
        for(int i = t; i != s; i = e[pre[i] ^ 1])
            w[pre[i]] -= flow[t], w[pre[i] ^ 1] += flow[t];
    }
    cout << ans1 << ' ' << ans2 << endl;
    return 0;
}

此外，其实这玩意还可以优化——多路增广！思想很简单，在求出 dis_t 的时候，不要急着用 flow_t 去更新，此时可能有很多条增广路的值都为 dis_t，显然他们可以同时增广。稍加思考，会发现这个过程就是 sap！需要注意的是，这个东西常数巨大，在一般情况下甚至跑不过朴素 ssp（过不了板子），但是在边权很小的图有奇效。

#include<bits/stdc++.h>
using namespace std;

const int N = 5010, M = 1e5 + 10;
int n, m, ans1, ans2;

int h[N], ne[M], e[M], w[M], w1[M], idx = 1;
void add(int a, int b, int c, int d)
{
    e[++idx] = b, w[idx] = c, w1[idx] = d, ne[idx] = h[a], h[a] = idx;
}

int tot, s, t;
int flow[N], dis1[N], pre[N];
int q[N], hh, tt;
bool in[N];
bool ssp()
{
    memset(flow, 0, sizeof(flow));
    memset(dis1, 0x3f, sizeof(dis1));
    memset(in, 0, sizeof(in));
    hh = tt = 0;
    flow[s] = INT_MAX, dis1[s] = 0, in[q[tt++] = s] = 1;
    while(hh != tt)
    {
        int t = q[hh++]; in[t] = 0;
        if(hh == N) hh = 0;
        for(int i = h[t]; i; i = ne[i])
            if(w[i])
            {
                int j = e[i];
                if(dis1[j] > dis1[t] + w1[i])
                {
                    flow[j] = min(flow[t], w[i]), dis1[j] = dis1[t] + w1[i], pre[j] = i;
                    if(!in[j])
                    {
                        in[q[tt++] = j] = 1;
                        if(tt == N) tt = 0;
                    }
                }
            }
    }
    return flow[t];
}

int dis[N], cnt[N], cur[N];
int sap(int x, int inflow)
{
    if(x == t) return inflow;
    int outflow = 0;
    for(int &i = cur[x]; i; i = ne[i])
        if(w[i] && dis[x] == dis[e[i]] + 1 && dis1[x] + w1[i] == dis1[e[i]])
        {
            int flow = sap(e[i], min(inflow - outflow, w[i]));
            w[i] -= flow, w[i ^ 1] += flow, outflow += flow;
            if(inflow == outflow || dis[s] >= tot) return outflow; 
        }
    if(!--cnt[dis[x]]) dis[s] = tot;
    cnt[++dis[x]]++, cur[x] = h[x];
    return outflow;
}

int main()
{
    cin >> n >> m >> s >> t;
    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), add(b, a, 0, -d);
    tot = n;

    while(ssp())
    {
        memset(dis, 0, sizeof(dis));
        memset(cnt, 0, sizeof(cnt));
        memcpy(cur, h, sizeof(cur));
        int flow = 0;
        while(dis[s] < tot) flow += sap(s, INT_MAX);
        ans1 += flow, ans2 += flow * dis1[t];
    }
    cout << ans1 << ' ' << ans2 << endl;
    return 0;
}

2.例题

基础运用：

P2469 [SDOI2010]星际竞速
建图好题？

这里的难点在于如何表示“水流必须要途经一个点”。如果水流直接流向汇点，那就不是“经过”而是“停止”了。
事实上，我们可以把每一个点拆成两个点 i 和 i'。还是上面说的，i\to t 要连边，同时 s\to i' 也要连边。剩余的就很简单了。

动态建图：

P2050 [NOI2012] 美食节
显然，如果一个厨师要做的菜的时间依次是 a1,a2\dots,a_k，则时间为 ka_1+(k-1)a_2\dots+a_k。考虑把一个单项式看做一个整体，那么每道菜的实际时间会受到系数 k 的影响。我们对厨师进行拆点，表示不同系数的厨师，则每个“单位厨师”只能做一样菜品。
正确性显然，但是时空……

由于“单位厨师”显然具有单调性，只有系数为 i 的厨师被选择了，i+1 才有可能被选择。考虑动态开点、动态连边即可。

通项：\frac{n\times(n+2)+(n\bmod2)-2}2

https://www.luogu.com.cn/record/138575712

5.圆桌问题

简单题，把人当做水，建虚拟点 s,t，每个单位的代表人数 r_i 意味着 c(s,i)=r_i，每个圆桌的人数限制 c_j 意味着 c(j,t)=c_j，相同单位的每个人的圆桌都不相同意味着 c(i,j)=1。跑最大流，如果 maxf=\sum r_i 则有解。

https://www.luogu.com.cn/record/136813729

6.最长不下降子序列问题

第一问显然。（关于我第一问求错了，后面两问对了这件事……）

第二问先将题目给定的偏序集建出来（建立虚拟源点和虚拟汇点）。于是题目转化为了最多可以划分成多少个长度为 s 的路径。注意到如果没有 s 的限制就好做多了，于是这玩意可以先跑一边最长路，检查一下每条边是否在最长路上，把那些不在的边去掉即可。
接着以源点和汇点直接跑最大流显然就是答案。

第三问就是第二问的 plus 版。只要懂了第二问，那么第三问就很简单了：把源点和 1 号点之间、n 号点和汇点之间分别连一条容量无穷大的边即可。
事实上，这玩意不需要重新开始跑。由于在残留网络上添加新边之后，可以接着跑最大流，所以无需清空，在第二问的基础上继续加即可。

https://www.luogu.com.cn/record/136661434

7.试题库问题

简单建模。
题面有些模糊，大意是每个题都有对应的类型，你可以决定将他归入哪一类（也就是最后每道题只有一种类型），最后使得每一类的题目数等于给定的值。

将类型看做左部的点、题目看做右部的点建立二分图，每道题向他对应的类型连边，边权为 1。然后把题目当做水，建立源点汇点，看它是否可以分配成功即可。（最大流是否等于 m）

https://www.luogu.com.cn/record/136968221

8.机器人路径规划问题

网络流 24 题中唯一一道暂未解决的题目！

对于这种题，我想如果把它作为论文题看待应该更合适。另外，由于数据本身有误，我们不以通过此题作为研究目标，而应是在尽可能优秀的复杂度内解决该问题。

这里就不赘述此题了，网络上也有若干关于此题目的讨论，可以在当中获取一些关于此题目前的研究成果。

9.方格取数问题

首先将问题转化为：从方格中删去一些数，使得删掉的数字总和最小。

这道题的突破口在于二分图，因为将相邻元素相连形成的图显然是二分图。由于删掉元素本身不好处理，所以这张初始的图很难再去表示“代价”这个信息了。考虑用额外的边表示代价，即从每个点引一条边出去，边权是点权。画出这张图，思考这张图怎么表示答案。
由于图上相邻元素不能同时选，容易想到用最小割的方式表示。显然割的是点不是边，也就是说那些代表点权的边是可以割的，连接关系的边不应该割掉，权值赋值为 +\infty 即可。建立源点 s 表示左部的点，t 表示右部的点，如果这个点没有被选，则代表这条边是割边。容易证明对于所有合法方案，这样割掉之后 s,t 都不再连通。对这张图跑最小割，就是被删掉的数之和。

https://www.luogu.com.cn/record/136823472

10.餐巾计划问题

有点类似上面的 P2469 [SDOI2010]星际竞速。

https://www.luogu.com.cn/record/137799479

11.航空路线问题

首先考虑求城市数。显然最后的形态是一个环，我们将它变为两条链，那么每条边都一定是从左往右连的。其中 2\sim n-1 这些点显然只能经过一次，这可以拆点解决。于是我们连边 s\xrightarrow21,n\xrightarrow2t，跑最大流即可表示一种方案。为了使城市最多，给每个城市加上一个“费用 1”，跑费用流即可。
方案输出也不难，无非就是找到那两条链，将其中一条倒序输出即可。

注意特殊情况：1\to n\to1，特判即可。

https://www.luogu.com.cn/record/138668286

12.软件补丁问题

没看出来和网络流的关系？据说可以费用流，有懂的大佬欢迎补充下。

首先数据范围一眼状压。
容易发现只有 2^{20} 种状态，考虑状压 DP，但是会有后效性。转移式非常简单，观察其本质，事实上就是一个最短路而已。直接上一个 dijkstra 即可。
代码实现中没有建图，因为可以直接转移。

https://www.luogu.com.cn/record/137267683

13.星际转移问题

分层图模板题？

显然答案不会太大，考虑暴枚答案。由于不同时间每个飞船的路线不一样，不太方便处理。我们可以把每个点都拆成 t 个（t 表示时间），然后每个飞船连边的时候显然除了位置改变，时间是要随之 +1 的。画在图上就变成了分层图的形式，前一层向下一层连边。

之前说过，跑分层图，我们不需要重新跑，只需要清空 dis,cnt,cur 跑，复杂度即可保证。不过虽然如此，显然看得出来这样的常数非常大，放到这道题是会 TLE 的。这里给出两种解决方法：

• 跑二分，虽然带 \log，但常数肯定比上面小；
• 用 EK \operatorname{or} Dinic，事实上，在分层图里，EK 的复杂度会减少到和 ISAP 同级，且常数显然很小，可以通过；当然 Dinic 更优，因为 Dinic 本身就是支持跑残留网络的，用不着我们 ISAP 的清空操作。

最后一句话：判无解！！！（调死我了）

https://www.luogu.com.cn/record/137598893

14.孤岛营救问题

也不需要网络流，bfs 即可解决。

鉴于 P 很小，考虑状压。于是直接 bfs 就可以过了。另外在实现的时候，没有必要区分墙和门，因为显然找不到 0 这种钥匙，直接把墙当做需要 0 号钥匙的门即可。

https://www.luogu.com.cn/record/138679559

15.汽车加油行驶问题

鉴于 k 的范围过小，考虑分层图，用层数表示油数，暴力建图即可。这样的边数、点数在普通的 ssp 算法中会 TLE，但是考虑到这里的总流量只有 1，所以相当于只是跑了一遍最短路而已。

注：当经过加油站的时候，强制加油，不能不加！

https://www.luogu.com.cn/record/140191315

16.数字梯形问题

又是缝合怪？都是最大费用最大流，建图不同，每一问拆开做。

1. 对于第一问，实际上就是限制了每一个点的流量至多为 1，拆点即可。
2. 第二问实际上就是把点的流量不超过 1 改为了边的流量不超过 1，反而更简单了。
3. 第三问更简单，去掉了所有的流量限制。

注意在复制代码的时候不要粗心大意，多测清空即可。

https://www.luogu.com.cn/record/140213256

17.运输问题

费用流模板题？
显然是一个二分图，点数和边数规模都不算大，直接根据题意模拟建图即可。注意，由于要求两个答案，不能直接在残留网络上面跑，只能重新建一遍图。

https://www.luogu.com.cn/record/140215085

18.分配问题

和前一道完全一样？（甚至更简单？）

https://www.luogu.com.cn/record/140215960

19.负载平衡问题

这里和上面邮票的那道题有点相似，利用的网络流的“自适应性”进行处理。每个点和 s,t 连边，从直观上看是错误的，但是仔细一想由于流量的不同，导致有些水并不能直接流入汇点。这时，这些水便会流经我们的“环”，产生代价。

https://www.luogu.com.cn/record/140216832

20.深海机器人问题

一眼看上去有点难度，仔细一看，好像并没有规定机器人的具体起点和终点，让我自己分配？这不成水题了吗？
然后调坐标调了很久……

https://www.luogu.com.cn/record/140229723

21.最长k可重区间集问题

费用流建模题，具体的建模参考题解。
但是本人非常的菜，什么都不会，于是使用了一种超级暴力的方法。具体如下：

首先肯定要连一条链，容量为 k，费用为 0，来限定最多 k 次。但是如何表示区间的代价呢？最开始想的是连接 s\xrightarrow[0]1l,r\xrightarrow[r-l]{1} t，但是错误性显然。
考虑如何修改：我们要使得每一组这样的边要么都选，要么都不选才是合法的。于是我建了一个虚点 i 表示这个区间，连边 s\xrightarrow[0]1i,i\xrightarrow[0]1t 表示不选这个区间，连边 i\xrightarrow[0]1l,r\xrightarrow[r-l]1i 表示选择。显然这样跑出来是正确的，但前提是得跑出来……
具体的，实际上这样是有正环的，跑带正环的最大费用最大流即可。

https://www.luogu.com.cn/record/138414772

22.最长k可重线段集问题

上面那道的加强版。

不用上面的奇怪解法了，我们来想一下标准解法。首先同样的画出数轴，每一个开区间我们用一条边直接连接首尾，表示选择了它。然后跑一个最大流为 k 的费用流即可。正确性可自行思考或参考题解。

回到此题，注意到，y 这一维实际上影响不大，我们直接把所有线段映射到 x 轴上，即可转化为上一道题。不过可惜的是，这样做只有 9 分，这也是称之加强版的原因。
考虑问题所在。当某条线段的 x_1=x_2 时，他是垂直于 x 轴的，映射过后就成了一个点。根据理论，我们希望这个点为实心点（显然其他那些都是空心的，这里的实心空心即为数学上的能否去取到），但是我们上面的方法处理不了实心的点。遂考虑拆点，将一个点变为线段即可。

https://www.luogu.com.cn/record/141299229

23.火星探险问题

P2045 方格取数加强版
这道题挺经典的，同时作为火星探险问题的弱化版，建议先把此题做了。

回到这道题，无非就是不能经过 1，经过 2 的价值是 1。直接拆点即可，将每个点拆为两个，即可控制第一次经过为 1，后续经过都为 0 的要求。
当然这个题恶心的是输出方案，直接对于每个机器人在图上跑一下就好了。

https://www.luogu.com.cn/record/141218320

24.骑士共存问题

题目给了一张图，其实已经算提示了：那张图告诉我们黑白染色过后一定会是一张二分图！
于是变为了二分图的最大独立集问题，实现方法很多。

https://www.luogu.com.cn/record/141220604

八、后记

感觉网络流真的非常玄乎，有些题如果不是标签都不会往这方面想。基本靠刷题，见过的多了自然就会了。

参考文献：
浅谈网络流的各种建模方法（好文力荐！）