网络流

title: 网络流
tags: 算法
date: 2022-11-22 16:39:38

本文章遵守知识共享协议 CC-BY-NC-SA ，转载时需要署名，推荐在我的个人博客阅读。

前置知识

图
深度优先搜索
广度优先搜索

网络流长什么样？

网络流的图一般是这种图：

网络流图示

每条边的最大流量如下图所示，求从4到3的最大流量。

仔细思考一下，可以得出最大流量应该是 50 ，每条边的实际流量应该是这样：

一种可行流

你的解法可能和我的不一样，类似于这样：

另一种可行流

网络流的性质

但是无论如何，一个可行的流应该满足如下条件：

容量约束

这个很容易理解，所有边的实际流量不能超过容量。

反对称性

假设 u 到 v 的流量是 $flow(u,v)$ ，则从 v 到 u 的流量是 $flow(u,v)$ 或 $-flow(v,u)$ 。

流量守恒

和电路有点像（随便在电路里画个圈，流入电流等于流出电流）。

对于除 $s,t$ 以外任意一个点，流入流量等于流出流量。

更形式化的说， $\sum_{x,u \in E}flow(x,u) = \sum_{u,y \in E}flow(u,y)$

用上面图中的一部分举例：

流量守恒

讲解

知道了这些性质，我们就应该求解网络最大流了。

EK算法

EK算法是一种非常简单且朴素的用于求解网络流的算法，需要使用深度优先搜索和广度优先搜索。

主要步骤如下：

找增广路
增广
回到步骤1，直到找不到增广路为止

这里引入一个网络流中十分重要的概念：反向边。

反向边具有如下规则：一条边增流时，反向边减流，反之亦然。

为什么要这样呢？因为我们的 bfs 第一次搜索出的路线可能不是最优的，所以我们需要反向边来给程序一个后悔的机会。

让我们模拟一遍，再次回到开始时的那张图：

第一次bfs

我们首先 bfs ，找到一条路径: 4->3。

正向边减流，反向边增流，最大流变为20，图变成了这样：

第一次bfs后的网络

此时反向边的作用就出来了，沿着反向边向回搜索，正向边增流，反向边减流，回到了搜索前的状态（这就是所谓反悔）。

多次重复这样的操作，直到原点与汇点不再联通为止。

甚至核心代码只有一行

while(bfs())update();

这是极其朴素的算法，但是这样的算法仍然存在许多缺点,比如每次都判断是否联通太过浪费，搜索方向不明确等等。

贴上bfs的代码：

bool bfs(){
  memset(vis,0,sizeof(vis));
  queue<int> q;
  q.push(s),vis[s]=1;
  incf[s]=inf; // 源点流量无限
  while(q.size()){
    int u=q.front();q.pop();
    for(int i=head[u];i;i=Next[i]){
      if(c[i]){
        int v=ver[i];
        if(vis[v])continue; // 不要重复添加
        incf[v]=min(incf[u],c[i]); // 这条链 （下一个节点到当前节点）最大流量应该为路径上最小
        pre[v]=i; // 设置当前节点的前一个
        q.push(v),vis[v]=1; // 继续搜索
        if(v==t)
          return 1; // 找到就退出，并标记找到
      }
    }
  }
  return 0; // 没找到就凉拌
}
void update(){
  int u=t; // 反向找回去，从t回到s
    while(u!=s){
    int i=pre[u]; // 上一个
    c[i]-=incf[t]; // 反向边减流 
    c[i^1]+=incf[t]; // 正向边增流
    u=ver[i^1]; // 实际上是正向边的上一个
  }
  maxflow+=incf[t]; // 更新最大流
}

dinic

前面提到， EK 算法缺点是每次都 dfs ，效率太低，所以我们需要 dinic 算法。

dinic 通过一次 bfs 可以实现多次增流，还可以避免扫描重复。

相对于EK算法，dinic的重复搜索更少，效率应该会更高。

bool bfs(){
    memset(d,-1,sizeof(d));
    queue<int> q;
    q.push(s),d[s]=0,cur[s]=head[s];
    while(q.size()) {
        int u = q.front(); q.pop();
        for(int i  = head[u]; i; i = Next[i]) { // 遍历每条出边
            int v= ver[i];
            if(d[v] == -1 && c[i]) {
                q.push(v); // 添加到队列
                d[v] = d[u] + 1; // 更新深度
                cur[v] = head[v];
                if(v==t)return true; // 搜索到终点就退出
            }
        }
    }
    return false; // 没搜索到就退出并标记失败
}
int dfs(int u, int limit) {
    if(u==t) return limit; // 到达就返回
    int flow = 0;
    for(int i=cur[u];i&&flow<limit;i=Next[i]){ // 遍历
        cur[u]=i;
        int v=ver[i];
        if(c[i]!=0&&d[v]==d[u]+1){ // 沿分层图深度+1方向搜索
            int f=dfs(v,min(c[i],limit-flow)); // 分配最大流
            if(!f)d[v]=-1; // 
            c[i]-=f,c[i^1]+=f,flow+=f; // 正向边减流，反向边增流
        }
    }
    return flow; // 返回最大流
}

int dinic(){
    int maxflow=0,flow=0;
    while(bfs()) // 判断联通并分层
        while(flow=dfs(s,inf)) // 还有增流的空间（一次bfs多次增流）
            maxflow+=flow; // 增流
    return maxflow;
}