曾经令我望而却步的知识,现在我要拿下它!

网络流的定义

​ 所谓网络或容量网络指的是一个连通的赋权有向图$D=(V,E,C)$, 其中$V$是该图的顶点集，$E$是有向边(即弧)集，$C$是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。

(来自百度百科)

​ “网络流”本身就是一个非常形象的名字.我们可以类比输水管网络或者河网.对于一张有向图,有一个起点$S$和终点$T$,我们可以类比成水源和入海口.在这个基本模型上我们又定义了一些概念:

• 源点:起点$S$, 即水只流出的点.
• 汇点:终点$T$,即水只汇入的点.
• 流量:一条河道(边)上流过的流量
• 容量:一条河道(边)能容纳的最大流量
• 残量:一条河道(边)剩余未使用的容量,即容量-流量.

其中,一条边$(u,v)$的流量常表示为$f(u,v)$,容量表示为$c(u,v)$

网络流的基本性质

1. 对于任意一条边,都有$f(u,v)\le c(u,v)$.其正确性显然,要不然河道就会溢出(或者水管爆裂)
2. 对于一条边$(u,v)$的反向边$(v,u)$,有$f(u,v)=-f(v,u)$.
3. $\forall x\neq S,x\neq T,\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)$.这句话意思是除了$S,T$以外,其他点的流入量和流出量总是相等的,不能储存水.

最大流

​ 最大流说的是整个网络的流量最大值.整个网络的流量就是$\sum_{(S,v)\in E}f(S,v)$,即从源点流出的流量之和.而一般可能河道的流量并不是被充分使用的,可能会有许多残量.最大流指的是尽量利用可利用的残量,能达到的最大流量.

​ 我们应该如何求解最大流呢?考虑一下,如果我们有一条从$S$到$T$的路径,上面所有边都没有被充分利用,那么我们是不是可以往这条路径中加水,从而在一定限度内增大流量呢?这条路径叫做增广路.形式化地,如果一条从$S$到$T$的路径$P$满足$\forall (u,v)\in P,f(u,v)<c(u,v)$,则称路径$P$是一条增广路.我们可以向这条路径中加入多少水呢?显然是加到其中一条边满了为止,之后再加流量也不会增大了.换句话说,我们流量增加的量就是增广路上的最小残量.

​ 接下来我们来讲解一下增广路的求法.

增广路算法(Dinic Only)

Dinic算法可以用来求二分图的最大匹配数,也可以用来求增广路.其基本思想如下:

1. 在残量网络上进行$BFS$来给节点分层
2. 在分层图上进行$DFS$寻找增广路,找到后回溯时更新这条边的剩余流量.

​ 其中,”残量网络”指的是由原图的所有节点和残量大于0的所有”未满”的边组成的图.我们假设$d[x]$表示从源点到$x$所经过的边数.然后按$d$对节点进行分层,这样我们最终一定会得到一张无环的图,即一个$DAG$.然后我们不断寻找增广路并向这条路中增大流量使得它不再是增广路.最终没有能够增广这个网络的路径的时候,这个网络流的流量就达到了最大值.

​ 但是,我们DFS是按照扫描出边的顺序来进行的,可能我们当前选择了$(u,v)$,但其实选择$(u,x)$来增广更优.因此我们要维护一个”反悔”操作.我们可以通过在反向边上加流量来达到.比如我们一开始选择了$(u,v)$,但是应该选择$(u,x),(y,v)$,这就相当于$(u\rightarrow v),(y\rightarrow v\rightarrow u\rightarrow x)$,让$(y,x)$路过的$(v,u)$和之前的劣解$(u,v)$相抵消,并一起流向了$x$,同时又有$(y,v)$,因此相当于反悔并选择了更优解.

​ 操作上,为了方便地维护相反边,我们可以使用”成对储存”的方法,把边的编号从2开始,即2,3互为反向边,4,5互为反向边.这样如果有一条边$x$,那么它的反向边就是$x\ xor\ 1$.

​ 我们已经说了$Dinic$算法的流程,接下来配合注释看一下代码实现.

#include <bits/stdc++.h>
#define inf 1145141919
#define N 50005
#define M 300005
using namespace std;

int n, m, S, T, noe, maxflow;
int to[M], len[M], nxt[M], head[N], dep[N], cur[N];
queue<int> q;//d指的是depth,即对图的分层,cur数组用来进行当前弧优化,下面会说到

inline void addedge(int from, int t, int l) { 
    len[++noe] = l, nxt[noe] = head[from], head[from] = noe, to[noe] = t;
    len[++noe] = 0, nxt[noe] = head[t], head[t] = noe, to[noe] = from;
    return;//这里的len指的是残量,一开始没有反向边,所以是0,而正向边没有流量流过,所以是满的.
}

inline bool bfs() {
    memset(dep, 0, sizeof(dep));//多次bfs要清空
    memcpy(cur, head, sizeof(cur));//cur数组指的是现在增广到哪一条边了,
    while (!q.empty()) q.pop();//记录cur的目的是忽略掉那些已经满了的没用的边.
    q.push(S), dep[S] = 1;//初始化
    while (!q.empty()) {
        int temp = q.front(); q.pop();
        for (int i = head[temp]; i; i = nxt[i])
            if (len[i] && !dep[to[i]]) {
                q.push(to[i]);
                dep[to[i]] = dep[temp] + 1;//分层
                if (to[i] == T)
                    return true;
            }
    }
    return false;
}

int dinic(int now, int flow) {//源点能为当前点提供的最大流量.
    if (now == T || !flow) return flow;//到了终点就回溯
    int ret = 0;//ret统计了从这个点出发的所有边得到的增广量
    for (int i = cur[now]; i; i = nxt[i]) {//只扫需要扫的边
        cur[now] = i;
        if (dep[to[i]] == dep[now] + 1 && len[i]) {//是图的下一层而且还有可以利用的容量
            int temp = dinic(to[i], min(flow - ret, len[i]));//递归下去,返回途中的最小流量
            len[i] -= temp, len[i ^ 1] += temp;//回溯时的增广操作
            ret += temp;//每个点可能有多条出边,流量变化是总和
        }
        if (ret == flow) return ret;//源点只能提供这些流量,再增广也没有意义了
    }
    if (!ret) dep[now] = -1;//如果扫完全部都没有得到任何增广量,这个点就没用了
    return ret;
}

int main() {
    scanf("%d%d", &n, &m);
    scanf("%d%d", &S, &T);//读入源点和汇点
    noe = 1;//成对储存的技巧
    for (int i = 1, x, y, z; i <= m; ++i) {
        scanf("%d%d%d", &x, &y, &z);
        addedge(x, y, z);//从x到y有一条流量为z的边
    }
    int flow = 0;//每次的增广量
    while (bfs())//如果还有可以增广的从S到T的路径
        while (flow = dinic(S, inf))
            maxflow += flow;//统计增广量
    cout << maxflow << endl;//输出最终结果
    return 0;
}

最小割

网络流的割

​ 割：设$C$为网络$G$中一些弧的集合，若从$G$中删去$C$中的所有弧能使得从源点$S$到汇点$T$的路集为空集时，称$C$为$S$和$T$间的一个割。通俗理解，一个图或网络的割，表示一个切面或切线，将图或网络分为分别包含源点和汇点的两个子集，该切线或切面与网络相交的边的集合，称为图像的割。

(百度百科)

​ 其实我们也可以类比无向图的割边.不同的是,如果割边是一条边,而割是边的集合,删去割边无向图将不会连通,而删去割中所有的边网络也会分成分别包含源点和汇点的两个没有边相连的部分.如果沿用河道的类比,那么一个割就是一些河道的集合,满足如果在这些河道中都建立水坝,将会没有水能够流向汇点.

最大流最小割定理

这个定理的内容非常简洁明了:在任何网络中,最大流量=最小割容量

​ 事实上可以感性理解这个定理.我们知道,网络的流量是从源点流出的流量之和,那么如果我们能找到一个割,就可以把这张图分成两个不相连的部分,一部分包含源点,一部分包含汇点.这样我们可以把这个网络想象成水管网络,节点是水管的交点,我们会发现所有的流量都从断点流出去了,无论流量有多大.所以我们发现任何一个流都一定$\le$ 任何一个割的容量.

​ 然后我们来考虑最大流和最小割之间的关系:流的上限(最大流)显然是受到了网络中容量最小的若干边的限制,而最小割显然是包括那些边的.换言之,正是因为一些比较窄的河道限制了所有从$S$到$T$的路径上的流量,所以最大流就只能达到这些窄河道的容量和.同时,由于把这些河道去除则会使得所有从$S$到$T$的路径都缺一块(即断掉),且这些河道是相对最窄的,所以它们构成了最小割,最小割的容量是这些窄河道的容量和.因此我们得到:最大流=最小割

例题:小M的作物

​ 这个题乍一看像是$DP$,但是实际上并不是.这道题体现了网络流的难点:建图.只要知道了图,求什么都好说,关键是以什么为流量,在谁与谁之间连边.我们首先考虑没有组合的情况,这种情况比较好连边,也就是以$0$点为$A$田地,$n+1$点为$B$田地,在田地与作物之间连接以收益为流量的边.然后我们考虑到,一个作物只能种在一块田地里啊,那就意味着在一种作物与两个田地的连边中,我们必须要切断一条.最终使得$A$田地和$B$田地没有同时相连的作物,换句话说,形成两个独立的部分.这不就是最小割模型吗?其实这种模型还有一个名字:两者取一式问题.

​ 然后问题来了,还有组合呢,这怎么办呢?我们知道,组合其实就是一组作物.这组作物共同拥有一个额外利益$c$.但是一条边显然不能同时指向两个点,所以我们建立一个虚点$x$同时代表组合内部的作物.可以结合下图理解.组$x$中含有$1$和$2$.作为”替身”,我们应该要求从$x$出发也能够走到$1,2$的出边,而且中途不能经过其他原有的边.因此我们从$x$向$1,2$连边,就可以直接走到$1,2$然后走它们的出边了.但是这条新边代表的是$x$和$1,2$的关系,而不是流量,所以为了不让它影响最终结果,我们把它设为“割不断”的边,也就是容量为$inf$.

​ 同时从题意来考虑,如果$1$被分给了$B$田地,那么就代表着从$A$田地出发是不能到达$1$的.然而从$A$田地到$1$有且只有两条道路:$0\rightarrow 1$和$0\rightarrow x\rightarrow 1$.这两条路径上各自只有一条可以割断的边$0\rightarrow 1$和$0\rightarrow x$.所以只要组合内的作物被分到$B$,连接$A$和组合点的边一定会被切断(即无法获得在$A$的额外利益),符合题意.像下面这样建图然后仍然求最小割就好了.

费用流

​ 对于一个网络,有时每条边$(u,v)$除了有容量的限制,还有费用的限制.这个费用通常以单位流量需要的费用$w(u,v)$的形式给出.也就是说当这条边的流量为$f(u,v)$的时候,这条边的总费用是$f(u,v)\times w(u,v)$,由此产生出一系列费用流问题.

最小费用最大流

​ 一个网络中花费最小的最大流称为”最小费用最大流”.显然,是在保证流量最大的基础上求最小费用.对于这种问题,我们将原先最大流中的”$BFS$寻找最大流”改为”$SPFA$寻找最小费用最大流”就可以了.要注意的是,记得我们当时建立反向边来通过抵消原先决策来实现反悔操作.同样,为了抵消原先操作,我们所建立的反向边的费用应该是负的.因为每次寻找的都是单位费用最小的增广路,所以最终的费用和也是最小的

​ 流程上是这样的:

      1. 用SPFA寻找满足以下条件的路径
- 可以增广
- 在增广路中总的单位费用最小
    2. 用dinic对这条路增广.

具体内容结合代码理解.

inline bool spfa() {//BFS改SPFA
    memset(dis, 0x3f, sizeof(dis));//dis[i]指的是从S到i的最小费用
    memcpy(cur, head, sizeof(cur));
    memset(vis, 0, sizeof(vis));
    while (q.size()) q.pop();
    q.push(S), dis[S] = 0;
    while (!q.empty()) {
        int temp = q.front(); q.pop();
        vis[temp] = 0;
        for (int i = head[temp]; i; i = nxt[i])
            if (len[i] && dis[to[i]] > dis[temp] + cst[i]) {//松弛操作,前提是还有剩余流量
                dis[to[i]] = dis[temp] + cst[i];
                if (!vis[to[i]]) {
                    vis[to[i]] = 1;
                    q.push(to[i]);
                }
            }
    }
    return (dis[T] != dis[0]);//如果dis[T]是inf,就代表没有增广路
}

int dinic(int now, int flow) {
    if (now == T || !flow) return flow;
    int ret = 0; vis[now] = 1;
    for (int i = cur[now]; i; i = nxt[i]) {
        if (len[i] && !vis[to[i]] && dis[to[i]] == dis[now] + cst[i]) {
            //有剩余流量,没有被访问,而且是增广路上的点
            int temp = dinic(to[i], min(flow - ret, len[i]));
            len[i] -= temp, len[i ^ 1] += temp;//增广
            ret += temp, mincost += temp * cst[i];//记录最小费用
        }
        if (ret == flow) return ret;
    }
    if (!ret) dis[now] = -1;//删掉没有贡献的点
    return ret;
}

感谢@_violet和@suwakow提供的帮助和参考