网络流初步

（寒假集训听了听i207M学长的课，感觉收获颇丰啊

定义

老样子，先从定义开始：

• 网络：网络是指一个有向图，$G=(V,E)$，V是点集，E是边集，对于任意的$(u,v)\in V$，都对应的有一个边权，这个边权代表一个限制性的东西，我们称之为容量。我们定义一条边属于一个网络里，有且仅有，联通且容量不为0。另外，特殊的是，在一个网络中必定存在两个特殊的点，源点S和汇点V，表示起点和终点。
• 网络流：我们规定从源点到汇点的所有流量之和为整个网络的流量。流必须满足以下的几个性质：

1. 容量限制，对于每一条边来说，我们经过其的实际流量不得超过它的最大流量

2. 斜对称性：每一条边和它的相反边（相反边是很重要的哦）的实际流量之和为0

3. 流守恒性：从源点流出的流量等于汇点所接受的流量

4. 剩余容量：最大流量-实际流量

我们可以将网络流形象地比作一个下水道系统（原谅我这个不太恰当的比喻），我们从城市的废水系统处接受总的水流（无限大），接收到源点，系统中分布着很多的管道，但是管道们有粗有细，有长有短，所以它们的极限流量不一样，我们要将废水运至汇点进行处理，那么我们就需要求出网络中的水流大小（汇点可以接收到的水流），但是不一样的是，在水流经过的时候，我们的管道中并不能储存或产生废水，从源点流入水就将从汇点流入水。

那么我们可以自然而然的想到：我最大可以从源点到汇点流过多少水呢？

引出下一个概念 ：最大流

最大流

定义

• 残量网络：在已经求得一部分容量后，所有的边的以自己的剩余容量所组成的一条网络称为残量网络，特殊的，在网络还并没有任何的流量的时候，残量网络就是原来的网络；
• 增广路：一条从源点到汇点的剩余容量都大于0的路径被称为增广路。（也可以说在残量网络的一条从源点到汇点的路径）
• 最大流：从源点到汇点的最大流量

虽然我们可以将网络流比作一个下水道系统，但实际上，这个下水道系统并不具有气压……各处的水面并不是一样平的，有的道路可能并不会被走过，有的道路可能会被走满，有的道路可能只会走一半。这就说明在一个网络里，不同的走的方案得到的流量是不一样的，所以我们就要进行最大流的求解。（这里只介绍OI中常用的最大流算法：dinic算法

dinic 算法求解最大流：

dinic算法本质上是求出一条一条的增广路，然后将增广路的流量都加起来之后的最大值就可以成为这个网络的最大流。

第一步是进行分层处理：首先用BFS对残量网络进行分层，我们设源点的层数为0（1也可以随你心情），那么一个点的层数就是它距离源点的最近距离（以边权角度来说的最近距离）

那么分层的目的是什么呢？

分层有两个目的：

1. 如果不存在增广路了，就直接停止算法进程
2. 确保我们找到的增广路是最短的（下面有原因
   接下来就是用dfs寻找增广路的过程了：我们每一次寻找增广路的时候，都只是寻找下一层的节点进行更新（只要有剩余容量就进行更新）

如果下面看代码的时候你会发现我会在反边里加上容量，原因是：如果仅仅是上述操作的话不一定更可以求出最大流，所以我们需要进行回溯，dfs寻找其他的增广路，那么我们就有必要在反边上进行改变，那样在回溯的时候就又可以变回原来的容量了（是在下面的另外一次BFS的时候的（但是我并不是很理解建反边的实际作用，或者说实际的流程）（希望有大佬科普）

dinic算法有两个优化：

1. 多路增广： 每次找到一条增广路的时候，如果残量网络并没有用完呢？我们可以利用参与部分流量，再找出一条增广路。这样就可以在一次的BFS中找到多条的增广路
2. 当前弧优化：如果我们当前的边已经被增广过了，那就没有必要在进行一次增广了，肯定没有可能去增广第二次了。那么我们下一次进行增广的时候就不需要再进行一次增广了。原因：在一条边被增广过了，只会有几种情况：一种是它上面的边溜过来的流量不够了，一种是它下面的边被填满了，另一种是它自己被填满了，不论是哪一种，我们如果再次对它进行增广，都不会产生任何贡献

这么一看dinic算法的复杂度其实挺不好的，毕竟每次进行新一轮的增广的时候都需要重新一次BFS，还需要一轮的DFS，复杂度似乎是 $O(N^2M)$ 级别的复杂度，但事实证明，dinic算法在平常的图中是可以跑过1e4~1e5级别的数据的（别问我为什么我也不知道）（是在加了两个优化的前提之下）

下面以洛谷模板题：网络最大流为例：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1010;
int d[maxn];
int n, m, s, t;
struct node
{
    int y, z, nex;
} e[10010 * 2];
int head[maxn], tot = 1, hd[maxn];/*tot=1是大细节……
如果你的邻接表在写的时候经常是用的++tot的话，
那写网络流的时候一定要记得把tot初始化为1，
因为下面的异或操作，
1异或之后是0而不是2……
奇数和偶数之间的异或就会乱掉
*/
void add(int x, int y, int z)
{
    e[++tot] = {y, z, head[x]};
    head[x] = tot;
}
int ans;
bool bfs()
{
    memset(d, 0, sizeof(d));
    queue<int> q;
    q.push(s);
    d[s] = 1;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = e[i].nex)
        {
            int v = e[i].y;
            if (e[i].z && !d[v])//残量网络
            {
                d[v] = d[x] + 1;
                q.push(v);
            }
        }
    }
    return d[t];
    //一遍普普通通的BFS，用来求我们的深度
}
int dfs(int x, int in)
{
    if (x == t || !in)
        return in;
    int out = 0;
    for (int &i = hd[x]; i && in; i = e[i].nex)//这里是当前弧优化
        //我不能够走某些边了（当前弧嘛），那么我直接从根源处扔掉它（就是邻接表）（下面每一次bfs是都是需要重新给赋值的
    {
        int v = e[i].y;
        if (e[i].z && d[v] == d[x] + 1)//必须是下一层的才可以进行增广，并且要在残量网络中
        {
            int res = dfs(v, min(e[i].z, in));
            e[i].z -= res;
            e[i ^ 1].z += res;//反边
            in -= res;
            out += res;
        }
    }
    return out;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, 0);
    }
    while (bfs())
    {
        memcpy(hd, head, sizeof(head));
        ans += dfs(s, 1e18);
    }
    cout << ans << endl;
    return 0;
}

例题

P2891 Dining G

题目链接

上来就给这道题还是很有意义的，因为这道题要用到网络流中一个经典的套路叫做拆点

拆点一般适用于那种对于一个点有流量限制的图中

这道题也很简单，首先是将食物与牛连边，牛对应自己喜欢的食物，然后是牛和饮料连边，对应自己喜欢的饮料

然后我们跑一遍最大流，思路就差不多了

但是这样对了但不完全对了

我们要对牛有一个容量限制，因为每头牛只吃一种食物，喝一种饮料，所以在牛处我们需要拆点

并且还需要对食物和饮料有限制，因为一种食物和一种饮料只有一个，所以在源点和汇点处连边的时候要记住容量为1

最后跑一遍最大流

最小割

定义：

对于一个网络来说，存在着一种边的划分，使得源点和汇点不连通，这个方案被称为是网络的一个割

最小割：顾名思义，边权和最小的一个割被称为最小割

最大流最小割定理

最大流等于最小割

例题

P2774 方格取数问题

题目链接

任意两个数没有公共边，并且取出的数最大

那么我们改变一下连边的策略的话：

我们把横纵坐标加起来为奇数的格子染成黑色，偶数的染成白色，我们让源点和黑色的格子连边，黑色的格子和相邻的白色格子连边，白色格子与汇点连边，这样构成了一个网络，那么我们求出这个网络的最小割就相当于求出了有什么点我是不选的，用所有点的权值和减掉最小割的权值就可以得到答案

容量的限制就可以是：黑点和源点之间的边容量为点权，白点和汇点之间的边容量也是点权，黑白点之间的边容量为inf，这样求出的最小割肯定是黑点或者白点的权值

最小费用最小流

（简称费用流）

定义

给定一个网络，这个网络不只是有容量限制，每一条边还有一个费用，代表流过1的流量需要的花费，要在最大流的前提下求出最小费用

和最大流算法差不多，只是我们在寻找增广路的时候是需要优先按照费用进行寻找而非边距，所以我们要用SPFA算法来进行分层

在建图的时候，是需要把费用也放到边的另一个权值上面的，那么反向边的费用呢？反向边的费用应该为正向边的相反数（显然把……总不能重复走

也有用dijkstra的，但我不会

时间复杂度极度玄学

理论上界nmf，f是最大流

以洛谷板子题：P3381为例子

例题：P2153 晨跑

题目链接

既然题目中说了：路程最短，时间最长，那这不就是费用流问题，时间为流量，路程为费用，我们在连边的时候，流量为1，并且拆点，把每一个点拆成两个并且流量为1，费用为0，这样保证这一个点只会经过一次，一条边的费用就是它的路程，然后跑一遍费用流就结束。

题目

P4016 负载平衡问题

题目链接

虽然在图上的环形问题很讨厌，但总比在序列上的好……（比如某群

（其实这道题完全可以不用网络流做，这可以用中位数做

我们对每一个点进行拆分，拆成两个不同的节点，一个是供应节点，另一个是需求节点，最后剩下的值应该是所有的平均数，那么边权就应该是当前值与平均数之间的偏移（当前值-平均数

如果偏移大于零说明这个点需要向外进行供应，就让它和源点连边，边权为偏移

小于零说明这个点需要向内输入，就让它和汇点连边，边权为偏移的绝对值

然后考虑相邻的节点之间的关系，由于相邻的节点之间是可以相互运送货物的，那么

相邻节点之间相互补充，把两个点的供应节点和需求节点相连，容量为无穷大，费用为1

相邻节点进行转运工作，把两个点的供应节点相连，容量为无穷大，费用为1

然后跑一遍费用流

P2770 航空路线问题

题目链接

我们先把题目进行一次转化：在网络上找到两条从源点到汇点的路径且不相交

那么我们可以很容易的把流量搞明白，每条边的流量为1，拆点，流量为1，最后源点出去的流量每一条边为1，汇点的流量在进行限制为2（或者在跑最大流的时候有while循环，只要流量已经为2了就停止增广（一次增广最多增加1的流量

那么我们考虑题目中的经过最多城市

我们走过的边中一定会含有我们没有走过的城市，那我们走过一条边就一定会到一个城市，那么我们将边的费用设置成1，跑一遍最大费用最大流就可以解决

题目还要求我们输出方案，那么直接进行一次DFS，将网络中 容量已经为0的边进行遍历，（容量为0说明走过，容量为1说明没走过

输出答案即可，注意不要重复输出最后一个点

（结尾需要加一个特判

P2766最长不下降子序列问题

题目链接

首先第一问可以直接用一个$n^2$dp搞出来，这里就先不说了吧

第二问开始就需要用到网络流了

由于每一个元素只能使用一次，那就说明如果用到网络流的话，这个元素可以进行拆点之后流量为1

然后呢？图怎么建呢？

我们考虑在dp的过程中我们都干了些什么？

我们在每一次转移之前都在向前找，找到比自己小于等于的数，转移。

那么，网络流时建边，也就是小数向大数建边

我们应该让当前点向前找，如果找到了一个数，它的dp值是这个点dp值减1，就连一条容量为1的边，源点向每一个dp值为1的点连边，每一个dp值为s的点向汇点连边

第三问呢？

第1和第n个点可以重复利用就说明……不需要拆点了！

没了

P2754 家园/星际转移问题

题目链接

并查集判断是否有解

这道题最好的方法是建一张分层图（经典套路之一）

分层图是什么意思呢？

就是我们以时间为轴，每一个时间点，，我们建n+2个点，上一个时间点是会对当前时间点有一定的影响的，那么就从上一个时间点想着一个时间点进行连边

回到这个题：这个题的要求是每一艘飞船都是有着自己的循环周期的，那么我们在两个不同的时间点连边的时候，就需要根据周期连边，容量为飞船的载客量

当然了，我们上一个时间点空间站是可能有人在的，那么，我们就让上一个时间点的人流到当前时间点也要建一条边，容量为正无穷。

源点向第一行第一个点连边，汇点和每一行的最后连边，容量为无穷大

每一层建之后跑一遍最大流，如果流量已经大于等于人数了，就停止，输出时间

P2045 方格取数加强版

题目链接

这道题还挺好的，拆点拓宽了一点思路

首先，我们还是要建出来这个网格图的，自己和相邻的点连边（细节看代码

连边之后我们会想到什么呢，方格走一次会有价值，但是走两次不会有价值，那么我们拆点

可是……拆点是限制流量啊

不不不……你错了，拆点的时候不只是可以限制流量

我们这道题将每一个网格进行拆点操作，拆完之后的点中间连两条边：一条容量为1，费用为边权，另一条容量为正无穷，费用为0

然后跑一遍最大费用最大流就可以了

P2053 修车

又是一道分层图的网络流呢

不过这道题还是很妙的，把我和Cloudysky困住了一小会来着

首先我们以工人为横轴，阶段为纵轴进行分层图的构建：

我们可以知道的是：对于倒数第i位，他会对自己后面的i位造成时间上的等待，那么我们考虑倒着建分层图，建i个工人修的倒数j辆车

这个节点向n个车连边，然后n个车向汇点连边，容量为1，向车连边的费用为当前阶段乘上时间

然后，我们考虑分层图上建边：

当前工人连第一个人的阶段应该连无穷大的流量，当前阶段连向下一个阶段的边流量也一样是无穷大，费用是0

然后跑一遍费用流就可以结束战斗了

就先写这一点点叭，以后还会有其他博客的哦

8971 个词，辛苦我了。

一些重要的东西

套路可以拆点

二分图最小点覆盖 = 最大匹配

二分图最大独立集 = 总点数减最小点覆盖

最小无交路径覆盖 = 总点数 - 最大匹配（建二分图之后出点连入点，S连出点，入点连T）

最小可交路径覆盖 = 传递闭包上的最小无交路径覆盖

最大权闭合子图转化成最小割做