网络流初探

2019.7.15，这个蒟蒻终于听懂了一听就很高大上的网络流~~其实是这个人过于zz~~，于是她准备来水一发博客。

前言

网络流解决的主要是这样一类问题：

给定一个源点、一个汇点，并给定(n)个点，(m)条边，每条边有一个最大流量，现从源点源源不断地注入可以视为无穷大的水流，问在汇点能接受的最大水流是多少？

网络流是类比水流的一种解决问题的方法，故下文为讲解方便，会经常使用水流来作类比。

正文

由于~~kma太菜了根本不会最高标号预流推进~~最高标号预流推进对于解决网络流问题速度的提升并不明显（虽然在某些特定的图上跑得挺快），故这里仅讨论增广路算法。

增广路

增广路：当从(S)开始流过一条路径并到达(T)，使得当前的最大流量能够增加，则这条路径称为一条增广路。

在增广路算法中，求最大流的问题就变成了不断求解增广路的问题，显然当图中已经不存在一条增广路时，当前的答案就是我们要求得的最大流。

那么具体怎么操作呢？

其实很简单，只需要从(S)点开始(bfs)，每次通过权值大于0的边，直到找到(T)为止，这个时候你就找到了一条增广路。那么找到这条增广路上权值最小的边，将边权记为(gmin)，然后让(max \_ flow)加上(gmin)，增广路上每条边的权值减去(gmin)。反复进行上述操作，直到找不到增广路即可。

为什么要在每条边的边权上减去(gmin)呢？当我们找到一条增广路，相当于这条边已经流了这么多流量，剩下能流的还有多少。对于一条边，显然我们只关心它还能流多少流量，而不是原本能流多少流量。

然而其实这样做有一个问题：万一流错了怎么办？

有一种东西叫反向边。

反向边

反向边就是拿给你反悔用的。

具体来说，我们在原图的每条边上都加一条反向边，且初始流量为0，当我们每次流经这条边时，我们在它的权值上减去当前流量，然后再在它的反向边上加上当前的流量。形象来说，我们接了一根返回去的水管。当我们每流经正向的水管时，扩容反向的水管，下次如果发现流错了，就从反向的水管流回去，这样正负相抵，就实现了一次反悔的操作。

好了，如果你上面的东西都看懂了，你已经成功学会了EK算法。

~~恭喜你成功学会了一个慢得要死的算法~~

总结一下：EK算法的核心：数次bfs找增广路，并通过反向边实现撤销操作。

当然，讲这么一大堆也并不是全是废话，毕竟接下来要说的算法本质上都是基于EK算法进行了优化。

Dinic

首先我们看看上面的算法有什么不足：

~~EK算法每次会遍历整个残量网络，但~~

等等我是不是讲掉了一个小知识点。

残量网络

残量网络的定义：在任意时刻，网络中所有节点及剩余容量大于0的边构成的子图称为残量网络。

简单来说，就是把那些已经流满的边丢掉，剩下来的图一定是原图的一个子图，这个图称为残量网络。

在(EK)算法中，每次(bfs)将遍历整个残量网络，但仅仅只找出一条增广路，效率较低。

分层图

设(d[x])表示节点的层次，即从(S)点到节点(x)经过的最少边数。在(Dinic)算法中，我们将满足(d[y] = d[x] + 1)的边((x, y))构建成一个分层图。每次(bfs)构造分层图，在分层图中使用(dfs)进行增广，一旦走到汇点，则向前回退并沿途更新边上边权，直到退到某个节点有另外的流量(>0)的出边，再从这个节点继续(dfs)下去。这样一次(dfs)能实现多次增广，当无法增广时再重新(bfs)构造残量网络和分层图并重复上述步骤。

总结一下：Dinic算法的几个步骤：

在原图上进行一次bfs，构造残量网络与分层图，将源点无法到达的点层次标为-1
在分层图上进行dfs并更改边权
当此分层图已经不能再进行增广时，回到步骤1
当汇点的层次被更改为-1（即与源点不连通时）退出算法

好的，现在我们讲完(Dinic)啦！OvO

ISAP

(ISAP)算法是在(Dinic)算法基础上的进一步优化。其本身也利用分层图的思想，但不同于(Dinic)的是，(ISAP)算法并不通过每次重新(bfs)来构造分层图，而是在每次(dfs)增广之后将所有已经没有可走增广路的点的深度更新。因为当这个点的深度可以被更新时，说明其在当前分层图下已经没有可行方案可以走了，于是将其重新分层，相当于动态分层的过程。

GAP优化

在执行(ISAP)算法的时候，如果当前出现了断层（某一层点的个数为0），那么说明已经没有增广路了，退出搜索即可。

讲完啦！完结撒花！✿✿ヽ(° ▽° )ノ✿

就直接上(ISAP)的代码啦：

代码：

#include <bits/stdc++.h>
#define N (400000 + 5)
#define M (400000 + 5)
#define int long long
using namespace std;
inline int read() {
    int cnt = 0, f = 1; char c = getchar();
    while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
    while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + c - '0'; c = getchar();}
    return cnt * f;
}
int tot = 1;
int n, S, T;
int to[N];
int flow[M];
int nxt[M];
int first[N];
int dep[N];  
int cnt[N]; 

void Add(int x, int y, int z) {
    nxt[++tot] = first[x], first[x] = tot, to[tot] = y, flow[tot] = z;
    nxt[++tot] = first[y], first[y] = tot, to[tot] = x, flow[tot] = 0;
}

void bfs_(int s) {
    memset(dep, 0xff, sizeof(dep));
    dep[s] = 0;
    cnt[0] = 1;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        for (register int i = first[p]; i >= 2; i = nxt[i]) {
            int v = to[i];
            if (dep[v] == -1) {
                ++cnt[dep[v] = dep[p] + 1];
                q.push(v);
            }
        }
    }
}

int max_flow;

int dfs_(int p, int f) {
    if (p == T) {
        max_flow += f;
        return f;
    }
    int u = 0;
    for (register int i = first[p]; i >= 2; i = nxt[i]) {
        int v = to[i];
        if (flow[i] && dep[v] == dep[p] - 1) {
            int uu = dfs_(v, min(flow[i], f - u));
            if (uu) {
                flow[i] -= uu;
                flow[i ^ 1] += uu;
                u += uu;
            }
            if (u == f) {
                return u;
            }
        }
    }
    if (!--cnt[dep[p]]) {
        dep[S] = n + 1;
    }
    ++cnt[++dep[p]];
    return u;
}
int m;
int x, y, z;
signed main(){
    n = read(); m = read(); S = read(); T = read();
    for (register int i = 1; i <= m; i++) {
        x = read(); y = read(); z = read();
        Add(x, y, z);
    }
    bfs_(T);
    while (dep[S] < n) {
        dfs_(S, 0x3FFFFFF);
    }
    printf("%lld", max_flow);
    return 0;
}