网络流学习笔记【更新中】

· · 算法·理论

网络流学习笔记

定义

在一个有向图上，存在一个源点 s 和汇点 t。

所有边从源点连出，最终连向汇点。

每条边有流量限制 w，即任何时刻这条边最多走 w 的流量。

题目一般会问从源点出发到汇点最多能有多少的流量。

比如下图就是一个网络流：

最大流

网络流的最基础的部分。

例题：洛谷 P3376 【模板】网络最大流。

首先最基础的建图没什么好说的。

EK(Edmonds-Karp) 算法

首先介绍 EK 算法。

我们引入增广路的概念。一条增广路是从 s 出发，t 结束的一条路径。这条路径的流量是好求的，就是路径上每条边流量的最小值。

在该算法中，我们会对整张图直接 BFS 多次求出所有增广路。答案即为所有增广路流量的总和。

但是，直接这样是有问题的。

比如这张图：

转自 OI-Wiki。

在这张图中，直接跑增广路是不优的。

所以我们继续引入退流的思想。

该思想的主要内容是，当之前一次决策中找到的增广路实际还可以被更多的扩展，此时的答案不是最优的，我们就把这条增广路去掉，重新去跑新的增广路。（感觉比较抽象？）

具体的，在实际建图时，我们会在反着建一条流量为 0 的边。

之后每次找到一条增广路时将路径上的所有正边的流量减去这条增广路的流量，所有反边的流量加上这条增广路的流量。

那么在决策不是最优时，我们会再去走一遍反边。一遍正边一遍反边就相当于没走。

这样就能保证正确性了。

放张图：

转自 【学习笔记】网络流-CCComfy の Blog

由于我们需要非常快速的找到一条边的反边，所有在网络流建图的时候，大部分 OIer 会选择使用链式前向星建图。但我偏不 但我仍然使用邻接矩阵建图，只不过需要多记录一点点东西。

我们在建边的时候记录下边的编号，并从任意偶数开始（我选择从 0 开始），这样编号为 op 的反边就是 op\oplus 1。千万不要写成 op+1 或 op-1！！！

在跑 BFS 的时候有一个小优化：当准备跑的边已经没有流量的时候，就不继续跑。看上去优化没啥用，但不加就会让你全部 TLE。

EK 的理论复杂度是 O(n\times m^2)，在边较少时跑的比较快。

然后放下代码：Link。

继续放几道例题：

CodeForces 78E Evacuation：题解

洛谷 P2763 试题库问题

简要题意：有 k 个标签和 n 道题，每个题目有一些标签。你需要给每个标签选一些题，并且每道题只能被一个标签选取。输出方案。

我们直接把每道题目和每个标签当成一个点。

那么连边显然可以是每道题目向它所属的标签连一条流量为 1 的边，每个标签向汇点连一条流量为它所需题目数量的边，源点向所有题目连一条流量为 1 的边。

然后跑网络流即可。

但是本题还需要输出方案。

我们不难发现，本题建出来的图大概长这样：

也就是说，我们在执行 Update 函数时，访问到的第一个结点是汇点，第二个结点是标签编号，第三个结点是题目编号。

那么我们就只要记录一下每一条增广路上经过的标签编号和题目编号，然后开一个 vector 记录即可。

其它都是差不多的，放一下 Update 函数的代码：

void update(){
  int x = t;
  queue<int> tmp;
  while (x){
    int o = pre[x];
    Dis[o] -= dis[t];
    Dis[o ^ 1] += dis[t];
    tmp.push(x);
    x = lst[o ^ 1];
  }
  while (tmp.size()){
    int o = tmp.front();
    tmp.pop();
    if (1 <= o && o <= n){
      ans[x].push_back(o);
    }else if (n + 1 <= o && o <= k + n){
      x = o - n;
    }
  }
}

Dinic 算法

首先 EK 算法在绝大多数情况下跑的很快，但在 m 较大时跑的会比较慢。

所以当 n 较小 m 较大时我们考虑使用 Dinic 算法。

事实上绝大多数题目直接用 Dinic 就够了。

Dinic 算法的核心是 DFS。但是它还是要用到 BFS。

其核心逻辑是：

1.首先利用 BFS 求出分层图。由于每一个点一次最多在一条增广路上，所以每个点在一次增广中的层级是不变的；

2.然后 DFS 按照分层图的顺序去求这条增广路的流量。

具体细节结合代码来看吧：

BFS 部分：

bool bfs(){
  for (int i = 0; i <= n; i++){
    level[i] = 0;
  }
  level[s] = 1;//分层，初始设为 1，vis 数组就可以顺便省了
  queue<int> b;
  b.push(s);
  while (b.size()){
    auto x = b.front();
    b.pop();
    for (auto v : g[x]){
      int w = Dis[v.id];
      if (!w || level[v.v]){
        continue;
      }
      level[v.v] = level[x] + 1;//v.v 是 x 在分层图上的下一个点
      if (v.v == t){
        return 1;
      }
      b.push(v.v);
    }
  }
  return 0;
}

DFS 部分：

int dinic(int x, int f){//当前在点 x，流量为 f
  if (x == t){//到汇点直接返回 w
    return f;
  }
  int rest = f, inc;//rest 是当前还剩下的流量，f - rest 就是这次增广跑出来的流量
  for (auto v : g[x]){
    int w = Dis[v.id];
    if (!w || level[v.v] != level[x] + 1){//没有流量或者 v.v 不是 x 在分层图的下一个点
      continue;
    }
    inc = dinic(v.v, min(rest, w));
    if (!inc){//没有流量 level[v.v] 就设为 0，之后不可能再跑 v.v
      level[v.v] = 0;
    }
    rest -= inc;
    Dis[v.id] -= inc;
    Dis[v.id ^ 1] += inc;//修改 rest 和边的流量
  }
  return f - rest;
}

主函数：

signed main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m >> s >> t;
  cnt = -1;
  while (m--){
    int u, v, w;
    cin >> u >> v >> w;
    add(u, v, w);
    add(v, u, 0);
  }
  while (bfs()){
    ans += dinic(s, 1e18);
  }
  cout << ans;
  return 0;
}

然后 Dinic算法就讲完了，撒花✿✿ヽ(°▽°)ノ✿

这样的 Dinic 的时间复杂度其实是没有保证的。

我们考虑这种图：

（当然这张图还不够大，不过假如链再长一些，连接 t 的点再多一些呢？）

此时我们的算法会每次从 1 跑到 9 后，无论之前有没有跑过，都重新把连接 9 的所有边都跑一边。

这样时间复杂度会直接炸掉。

怎么去优化呢？我们在此引入一个新的方法：当前弧优化。

事实上「当前弧优化」就是「当前边优化」，只是翻译过来变了，然后就没改了。

当前边优化的内容也十分简单。

我们考虑当前面的边已经被榨干了的时候前面的边再去跑一遍是不优的。

所以我们记录当前跑到了第几条边，然后之后从下一条边开始跑就好。

代码中体现出来就是这样：

  for (int &i = tmp[x]; i < g[x].size(); i++){
    // Do something.
    if (!rest){
      break;
    }
  }

千万注意，在用了当前弧优化后，一定要记得判 res 是不是已经为 0。不然 res 已经为 0 你还继续往下跑，这样记录的 tmp[] 就有问题了。

那么此时 Dinic 的时间复杂度就为 O(n^2m)。

然后 tmp[] 每重新跑一遍 BFS 就要更新。这个应该好理解。

同时判断的代码最好放循环最后，详见 Link 或保存站：Link。

然后真的就讲完了。

以下是例题部分。

洛谷 P2774 方格取数问题

简要题意：n\times m 的网格，每个格子有一个数。你需要从这些格子中选出一些数，但是相邻的格子不能都选。求最大和。

先引入一个定义：最小割。

在一个网络流图中，我们可以钦定一些边的流量变为 0，代价是这些边的流量和。

当钦定完后 s 和 t 变得不联通，我们就认为选出来的这些边是一个割。

最小割就是使得 s 和 t 不联通的最小代价。

在此介绍一个定理：最大流最小割定理。

最大流最小割定理的内容是：一个网络流图的最小割等于最大流。

提供一个感性的证明：要想要 s 和 t 不联通，那么其之间的所有路径都应该被删除。显然的，我们会选择流量小的边删除。而与最大流类似的是，一条增广路的流量就是路径上流量的最小值，也就是我们计划删除的边。

所以最小割等于最大流。

那么接下来看到这道题。

我们注意到相邻的格子都不能多选，于是就有了一个比较常用的 Trick：黑白染色。

我们将黑色的格子与 s 连边，白色的格子与 t 连边，相邻的格子连边。

然后跑网络流即可。

主函数：

signed main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  cnt = -1;
  t = 1e5;
  for (int i = 1; i <= n; i++){
    for (int j = 1; j <= m; j++){
      cin >> a[i][j];
      sum += a[i][j];
      if ((i + j) % 2){
        add(s, i * m + j, a[i][j]);
        add(i * m + j, s, 0);
      }else {
        add(i * m + j, t, a[i][j]);
        add(t, i * m + j, 0);
      }
    }
  }
  for (int i = 1; i <= n; i++){
    for (int j = 1; j <= m; j++){
      for (int k = 0; k < 4 && (i + j) % 2; k++){
        int dx = i + fx[0][k], dy = j + fx[1][k];
        if (1 <= dx && dx <= n && 1 <= dy && dy <= m){
          add(i * m + j, dx * m + dy, 4e18);
          add(dx * m + dy, i * m + j, 0);
        }
      }
    }
  }
  while (bfs()){
    int x = dinic(s, 4e18);
    sum -= x;
  }
  cout << sum;
  return 0;
}

费用流

最小费用最大流

现在一条边不仅有流量限制，还有需要的费用。

你需要保证在最大流的基础上费用最小。

事实上实现的做法和纯最大流差不多。

在 EK 中，我们把最少步数换成最小长度（费用），把 BFS 换成 SPFA（因为可能有负边权）即可。

Dinic 同理改一下即可。

然后注意一下连反边的时候边权也要取相反数，应该很好理解。

板子：洛谷 P3381 【模板】最小费用最大流。

代码放一下吧：Link。

洛谷 P2517 [HAOI2010] 订货。

题意简述：第 i 个月进货的单价 d_i 元，上个月没卖完的货存放至下一个月的单位费用需要 m 元，仓库容量为 S，第 i 个月至少需要 U_i 单位货物。假设最开始没有货物，求满足 n 个月的需求的最少成本。

由于本题实在没有什么其他状态，容易想到将每个月份作为点向源点连边，同时也向汇点连边。

那么向源点连边时流量为 +\infty，花费为 d_i。

然后向汇点连边时将流量设为 U_i，花费设为 0，就可以限制每个月都需要 U_i 单位货物。

并且由于上个月的货可以留存到下个月，那么就可以直接让点 i 向点 i+1(1\le i<n) 连一条流量为 S（因为仓库最多存下 S 单位货物），花费为 m 的边。

然后跑网络流即可。

主函数代码：

signed main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m >> S;
  for (int i = 1; i <= n; i++){
    int x;
    cin >> x;
    add(i, t, x, 0);
  }
  for (int i = 1; i <= n; i++){
    int x;
    cin >> x;
    add(s, i, 1e9, x);
  }
  for (int i = 1; i < n; i++){
    add(i, i + 1, S, m);
  }
  while (bfs()){
    update();
  }
  cout << cost;
  return 0;
}

洛谷 P2053 [SCOI2007] 修车

题意简述：有 n 位车主带着他们的辆车在时刻 0 到达了修车处，修车处共有 m 名技术人员，第 j 名技术人员修第 i 辆车的时间是 t_{i,j}。求所有车主等待时间的平均值的最小值。

咕咕咕

上下界网络流

无源汇上下界可行流

1.没有指定源点和汇点；

2.每条边有流量的上界和下界；

3.每个点流入和流出的流量守恒，包括虚拟的源点和汇点。