网络流学习笔记

# 网络流学习笔记

## 什么是网络流？

一个有向图，有源点汇点 $S,T$，边有容量 $c$，就是网络。

网络流就是在网络上从源点到汇点整个流，让每条边的流量都小于容量，而且除源点和汇点外都要满足流量平衡。

可以理解为有一个水管网络，有一些节点，由单向水管连接，水管各有粗细。流就是从 $S$ 到 $T$ 输水，且 $S$ 出发的水和 $T$ 接收到的水一样多，并且每个节点出入都一样~~不能无中生水或撑爆节点~~。

## 最大流

在满足流量小于容量的情况下，$S$ 最大能流多少到 $T$。换句话说，就是水管不爆，能运多少水从 $S$ 到 $T$。

怎么求最大流呢？

### Edmonds–Karp 算法

最朴素的做法就是贪心。

每次 BFS，如果 $S$ 到 $T$ 之间有一条路径，且这些边上都没有流满，此时我们就可以让它从这条路径流，那么流就会加上这些边容量的最小值。这叫增广，找到的路径叫做增广路。

然而贪心不一定正确，于是我们需要能反悔。所以我们加上反向边，容量初始为 $0$（正向边没流相当于反向边流满）。最后计算时不仅要在正向边加上流量，**反向边也要减少对应的流量**。

如果一次增广流经了一条反向边 $<u,v>$，相当于把一条路径切成两半。原来 $S-u-v-T$ 的路径变成 $S-u-新的增广路-T$ 和 $S-新的增广路-v-T$[^1]。

此时再进行 BFS，它就对了。

这就是 **Ford–Fulkerson 增广** 中的 **Edmonds–Karp 算法**。它的复杂度是 $O(|V||E|^2)$。这玩意复杂度实在高而且容易卡，所以算法竞赛中经常会用接下来即将介绍的 **Dinic 算法**。

### Dinic 算法

容易发现，每次增广都 BFS 一遍，复杂度太高了。有没有什么办法可以优化呢？

考虑对原图进行 BFS 分层后跑 DFS。每次 DFS 只会走向更深一层的点，当一条边无法再增加流（流满了）那么我们就跳过这条边继续下一条。

这个算法的时间复杂度是 $O(|V|^2|E|)$ 的，不过实际复杂度比较玄学，跑的飞快。

为了保证时间复杂度，Dinic 算法会添加 **当前弧优化**，具体就是当这条边无法再增加流时，我们下次进行增广时会跳过这条边，从下一条边开始增广。不过 **在 BFS 时应该把上次 DFS 的当前弧取消**，因为跳过的一些边原来可能深度不满足要求而现在满足了，不取消就会出错。

板子：

[P3376 【模板】网络最大流](https://www.luogu.com.cn/problem/P3376)

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

const int N = 205, M = 5005;
//#define int long long

struct edge {
    int nxt, v, c, f;
    edge() {}
    edge( int nxt, int v, int c ) : nxt( nxt ), v( v ), c( c ) {}
} e[M << 1];
int head[N], now[N], cnt = 1;
void add( int u, int v, int c ) {
    e[++cnt] = edge( head[u], v, c );
    head[u] = cnt;
}

int n, m, s, t, dep[N];
queue<int> q;

bool bfs() {
    memset( dep, 0, sizeof dep );
    q.push( s );
    dep[s] = 1;
    now[s] = head[s];
    while( !q.empty() ) {
        int u = q.front(); q.pop();
        for( int i = head[u]; i; i = e[i].nxt ) {
            if( e[i].c > e[i].f && !dep[e[i].v] ) {
                dep[e[i].v] = dep[u] + 1;
                now[e[i].v] = head[e[i].v];
                q.push( e[i].v );
            }
        }
    }
    return dep[t];
}

long long dfs( int u, long long flow ) {
    if( u == t || !flow ) return flow;
    long long ret = 0;
    for( int i = now[u]; i; i = e[i].nxt ) {
        now[u] = i;
        int v = e[i].v, d;
        if( dep[v] == dep[u] + 1 && ( d = dfs( v, min( flow - ret, 0ll + e[i].c - e[i].f ) ) ) ) {
            ret += d;
            e[i].f += d, e[i ^ 1].f -= d;
            if( flow == ret ) return flow;
        }
        
    }
    return ret;
}

long long dinic() {
    long long ans = 0;
    while( bfs() ) {
        //cout << 1 << endl;
        ans += dfs( s, 1e15 );
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio( 0 ), cin.tie( 0 ), cout.tie( 0 );
    cin >> n >> m >> s >> t;
    for( int i = 1; i <= m; ++i ) {
        int u, v, c;
        cin >> u >> v >> c;
        add( u, v, c ), add( v, u, 0 );
    }
    cout << dinic() << endl;
    return 0;
}
```

## 最小割

最小割就是割掉一些边使得 $S,T$ 不连通，要求割掉的边容量最小。

最小割等于最大流。可以感性理解一下，流最大的时候说明不能再增广，此时一定能断掉总和与流相等的一些边来达成目标，所以最小割一定不比它大；又如果少一些流量一定会导致还有增广路，所以最小割一定不必它小。所以最小割等于最大流。

所以求最小割也可以直接套 Dinic 板子。

## 费用流

即最小费用最大流。

### SSP 算法

我们发现 EK/Dinic 算法无法求解费用流的原因就是 bfs。

于是我们可以把 bfs 换成——

> **关于 SPFA**
>
> - 它死了。

额，好吧，Dijkstra 改改也行。~~不过 SPFA 多香啊~~

不过 SSP 算法的时间复杂度是和值域有关的。~~不过网络流题应该不会卡这个~~

板子（使用 EK 实现）：

[P3381 【模板】最小费用最大流](https://www.luogu.com.cn/problem/P3381)

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5,M=5e4+5;
struct Dinic{
    struct edge{
        int u,v,f,c,nxt,w;
    }e[M<<1];
    int head[N],n,m,s,t,dis[N],lst[N],cnt,flow[N],lst2[N],sum;
    int ans,floww;
    bool vis[N];
    queue<int>q;
    inline void add(int u,int v,int w,int c,int f){e[++cnt]={u,v,f,c,head[u],w},head[u]=cnt;}
    inline bool about_spfa_he_revive(){
        memset(dis,0x3f,sizeof dis);
        flow[s]=INT_MAX;
        memset(lst,0,sizeof lst);
        q.push(s);
        vis[s]=1,dis[s]=0;
        bool can=0;
        while(q.size()){
            int u=q.front();q.pop();
            vis[u]=0;
            if(u==t){can=1;continue;}
            for(int i=head[u];i;i=e[i].nxt){
                int v=e[i].v,f=e[i].c-e[i].f,w=e[i].w;
                if(!f)continue;
                if(w+dis[u]<dis[v]){
                    dis[v]=dis[u]+w,flow[v]=min(flow[u],f),lst[v]=i,lst2[v]=u;
                    if(!vis[v])q.push(v),vis[v]=1;
                }
            }
        }
        return can;
    }
    inline void dinic(){
		while(about_spfa_he_revive()){
			//cerr<<1;
			//cerr<<flow[t]<<'\n';
            int f=flow[t];
            floww+=flow[t];
            ans+=dis[t]*f;
			//cerr<<1;
            for(int i=t;i!=s;i=lst2[i]){e[lst[i]].f+=f,e[lst[i]^1].f-=f;}
        }
    }
    inline Dinic(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cnt=1;
        cin>>n>>m>>s>>t;
        for(int i=1;i<=m;++i){
            int u,v,w,c;
            cin>>u>>v>>c>>w;
            add(u,v,w,c,0),add(v,u,-w,0,0);
        }
        dinic();
        cout<<floww<<' '<<ans<<'\n';
    }
}a;
int main(){
    return 0;
}
```

## 上下界网络流

这个作者很懒，什么也没留下(·^·)

---

[^1]: 这样说并不完全准确，因为有可能只影响到了一半（半条路径被改变），或者一次影响到了多条路径。不过此例只是辅助理解，正确性方面可以稍微忽略。