网络流学习笔记

网络最大流

原版

板子没什么好说的，代码：

struct flow {
  int head[N], nex[M << 1], tot = 1, dep[N], S, T, cur[N];
  bool vis[N];
  struct E {
    int to, nxt, flow;
  } edge[M << 1];
  void ad(int x, int y, int z) {
    edge[++tot] = (E) {x, y, z};
    nex[tot] = head[x]; head[x] = tot;
  }
  void add(int x, int y, int z) {
    ad(x, y, z);
    ad(y, x, 0);
  }
  bool bfs() {
    queue <int> q; fill(dep + 1, dep + 1 + n, 0);
    q.emplace(S); dep[S] = 1;
    while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int i = cur[u]; i; i = nex[i]) {
        int v = edge[i].nxt, w = edge[i].flow;
        if (w > 0 && !dep[v]) {
          dep[v] = dep[u] + 1;
          q.emplace(v);
        }
      }
    } return dep[T] > 0;
  }
  int dfs(int x, int flow) {
    if (x == T) return flow;
    vis[x] = 1;
    int res = 0;
    for (int &i = cur[x]; i && res < flow; i = nex[i]) {
      int v = edge[i].nxt, w = edge[i].flow;
      if (w > 0 && !vis[v] && dep[v] == dep[x] + 1) {
        int k = dfs(v, min(flow - res, w));
        if (!k) vis[v] = 1;
        else {
          edge[i].flow -= k;
          edge[i ^ 1].flow += k;
          res += k;
        }
      }
    } 
    vis[x] = 0;
    return res;
  }
  i64 dinic() {
    i64 ans = 0;
    copy(head + 1, head + 1 + n, cur + 1);
    while (bfs()) {
      fill(vis + 1, vis + 1 + n, 0);
      ans += dfs(S, INT_MAX);
      copy(head + 1, head + 1 + n, cur + 1);
    } return ans;
  }
} dc;

预流推进

先咕着。

无源汇上下界可行流

上下界：即每条边都有流量限制，流过第 $i$ 条边的流量一定需要在 $[L_i, R_i]$ 之间。
可行流：是否存在流满足每个点的流量平衡，不需要最大化。

这里的流量平衡指的是，对于每个点，流入它的流量等于流出它的流量。

每条边的流量至少是 $L_i$ ，所以可以将所有边的流量全部赋成 $L_i$ ；然后再考虑将某些边的流量改变使得整个图满足条件。

于是，我们转化了问题：每条边的流量限制是 $[0, R_i - L_i]$ ，每个点初始时有流入它的流量和流出它的流量，使新图流量平衡。

这样相当于没有下界了，但是网络流还是没办法做这种问题。还需再转化一步，思考最大流中哪些点不满足流量平衡：源点和汇点。所以我们让它们发挥作用，具体地：设 $in_x$ 和 $out_x$ ，含义分别是初始时流入 $x$ 的流量和流出 $x$ 的流量，满足：

$\begin{cases} in_v = \sum\limits_{(u, v, L, R) \in E} L \\ out_u = \sum\limits_{(u, v, L, R) \in E} L \end{cases}$

（注意上面式子中的 $(u, v, L, R)$ 是有向边，表示 $u \to v$ 有一条上下界为 $[L, R]$ 的边）

新建虚拟源汇点 $S, T$ ，对于一个点 $x$ ，如果：

$in_x > out_x$ ，那么连一条 $S \to x$ 的边，上界是 $in_x - out_x$ 。
$in_x < out_x$ ，连一条 $x \to T$ 的边，上界是 $out_x - in_x$ 。
$in_x = out_x$ ，不连边。

在新图上跑最大流，这样只需要判断新边是否满流，因为一条边连向 $S, T$ 的边满流就代表这条边流量平衡了。

算法流程：

对于原图的边 $(u, v, L, R)$ ，在新图上建 $(u, v, R - L)$ 。
统计 $in_x$ 和 $out_x$ 。
对每个点的 $in_x$ 和 $out_x$ 讨论，再对虚拟源汇点处理。
跑最大流得到 $\text{maxflow}$ ，判断是否满足 $2 \cdot \text{maxflow} = \sum\limits_{i = 1}^n |in_i - out_i|$ ，如果满足就存在可行流，否则不存在。

有源汇上下界可行流

考虑转化成无源汇上下界可行流，也就是说多了两个点不满足流量平衡。

假设原图的源点汇点分别是 $s, t$ （用大小写来区分虚拟源汇点 $S, T$ ）。那么连一条 $t \to s$ 的流量限制为 $+\infty$ 的边就可以转化成无源汇上下界可行流了。因为 $s$ 流出的流量一定等于流入 $t$ 的流量，新建了边后 $s, t$ 满足流量平衡。

有源汇上下界最大流

现在要求最大流了，所以考虑找出一组可行流，再将其最大化。

最大化的方式也很简单，但我不会证，就是先跑一遍有源汇上下界可行流，再撤去 $(t, s, +\infty)$ 这条边，在残量网络上以 $s, t$ 为源汇点跑一遍最大流。两遍最大流的答案加起来就是答案。可以感性理解一下，严格证明是困难的。

例题：【模板】有源汇上下界最大流

区间覆盖模型

区间覆盖模型主要解决一流对多流的问题。

直接上例题：最长 $k$ 可重区间集问题。

题意

给定 $n$ 个区间，你需要选择一个区间集合，满足数轴上的每个点最多被 $k$ 个区间覆盖。每个区间的权值是这个区间的长度，求合法区间集合的权值和最大值。

上面所有区间都是开区间。

题解

考虑一种比较简单的建图：每个区间向它覆盖的点连边，接着点连汇点，区间连源点。

但是这样是错的，因为 1. 被覆盖 $k$ 次这个限制不好表示. 2. 出现了一流对多流的情况，流量不好赋。

考虑解决问题 $2$ 。显然有结论：区间端点的覆盖次数在任意时刻都是端点覆盖次数最大值。所以非端点的点是无意义的。

我们发现网络流就像一条水流，也许可以用这条水流的路径来表示某些东西。

于是此题的建模方式就是：

建立虚拟源点汇点 $S, T$ ，离散化下来所有端点，并排序。
第 $i$ 个端点连接第 $i + 1$ 个端点， $S$ 连第 $1$ 个，最后一个连 $T$ 。流量均为 $k$ ，费用均为 $0$ 。
对于 $n$ 个区间， $l$ 连接 $r$ ，流量为 $1$ ，费用为 $len$ 。
跑最大费用最大流，从 $S$ 出发的流量设成 $k$ 。

思考问题 $2$ 的解决方式在这个图上的体现，可以发现流量会从区间左端点分叉，又在区间右端点聚集。这样一流对多流的问题就不存在了。

继续思考问题 $1$ ，也就是这个算法的正确性。对于不交的区间，模拟一下可以发现这个做法没有问题。而对于相交的区间，由于初始流出去的流量为 $k$ ，所以当一个点 $x$ 被覆盖 $k$ 次时，流过 $x \to (x + 1)$ 这条边的流量就已经是 $0$ 了，没有多余的流量来多覆盖一次。于是问题 $1$ 也解决了。

总结

这类题的建模大概是长这个样子：

源点连第一个点，第 $i$ 个点连第 $i + 1$ 个点，最后一个点连汇点，附上合适的流量和费用。

对于区间 $[l, r]$ ， $l$ 连 $r + 1$ （如果是开区间就连 $r$ ），附上合适的流量和费用。

这种模型建图时要多注意流量限制，避免再次出现一流对多流的情况。

练习题

最小割

最小割：在一个有向图上，每条边有一个权值，两个点的最小割定义为：割断一些边，使两点不联通的最小代价。

最大流最小割定理：最大流（以 $s, t$ 为源汇点）等于最小割（割断 $s, t$ 之间的边）。

最小割树

考虑一个问题：给定一张无向图， $q$ 次询问任意两点的最小割。

一种显然的方式是每次询问都跑一遍最小割，但是这样复杂度较劣，不能接受。

考虑建立一棵最小割树，利用树上两点路径唯一的性质来解决该问题。

最小割树的定义

树边 $(u, v)$ 的边权是 $u, v$ 的最小割。
删掉 $(u, v)$ 后形成两棵子树的点集对应原图的最小割方案的两部分。
任意两点 $s, t$ 的最小割是最小割树上 $s, t$ 路径上的最小边权。

最小割树的性质

严格的最小割树是难以建立的，大多数时候我们是不需要知道具体的最小割方案的，所以我们构建的一般都是“等价流树”，即只满足“任意两点 $s, t$ 的最小割是最小割树上 $s, t$ 路径上的最小边权”的树。不少人都认为最小割树等价于等价流树，但实际上这是不严谨的。（具体可以参照2016年集训队论文集）。

下面定义 $\lambda(x, y)$ 表示 $x, y$ 的最小割。

引理 1：对于任意三点，有 $\lambda(a, b) \ge \min(\lambda(a, c), \lambda(b, c))$ 。

证明：设割断 $a \leftrightarrow b$ 和 $a \leftrightarrow c$ 的最小割为 $\alpha$ ，割断 $a \leftrightarrow b$ 和 $b \leftrightarrow c$ 的最小割为 $\beta$ ，割断 $a \leftrightarrow c$ 和 $b \leftrightarrow c$ 的最小割为 $\gamma$ ，则原式可以转化成 $\min(\alpha, \beta) \ge \min\{\min(\alpha, \gamma), \min(\beta, \gamma)\}$ ，这是个恒等式。故原式成立。
引理 2：假设去掉 $a \leftrightarrow b$ 最小割后得到两个点集，与 $a$ 相连的记作 $A$ ，其它记作 $B$ 。那么 $\forall p \in A, q \in B$ 有 $\lambda(a, b) \ge \lambda(p, q)$ 。

证明：假设 $\lambda(a, b) \le \lambda(p, q)$ ；那么根据假设，割掉 $a \leftrightarrow b$ 后 $p, q$ 必须联通，但这时可以有路径 $a \to p \to q \to b$ 使 $a, b$ 联通。所以假设不成立，原式得证。

根据上面两条引理，可以推出：对于任意两点 $x, y$ ，假设 $(s, t)$ 是最小割树上 $x, y$ 路径上边权最小的边。根据引理 1 有 $\lambda(x, y) \ge \lambda(s, t)$ ，根据引理 2 有 $\lambda(x, y) \le \lambda(s, t)$ ，所以得出 $\lambda(x, y) = \lambda(s, t)$ 。

建立最小割树

使用分治，每次取分治区间的任意两点 $(a, b)$ ，求出最小割，并记录下 Dinic 时最后一次 bfs 的 dep 数组。如果 $dep_x > 0$ 说明在 $a$ 侧，否则在 $b$ 侧。将这两组点分别分治，就能建出最小割树。

例题：【模板】最小割树

最大权闭合子图模型

直接上一道例题。

简要题意

给定 $n$ 个实验项目和 $m$ 种实验仪器。实验项目只能做一次，实验仪器可以用多次。

做实验 $i$ 可以赚 $a_i$ 元，配置实验仪器 $j$ 需要 $b_j$ 元。

选择做哪些实验和配置哪些仪器，求最大收益。

解题思路

如果将实验项目和实验仪器都抽象成点，并且一个实验项目将它用到的实验仪器连边，那么这个问题转化成了：

左侧有 $n$ 个点，点有正权，右侧有 $m$ 个点，点有负权。选择一个点就必须选择其后继点，求最大权值和。

这是一个经典的网络流问题。如果一个点被选择了其后继必须选择，则称该图是闭合的，因此该问题称：最大权闭合子图问题。可以使用最小割解决，具体的建图方式为：

新建虚拟源汇点 $S, T$ 。

将 $S$ 和所有正权点连边，流量为该点权值；

将所有负权点和 $T$ 连边，流量为该点权值相反数；

对于原图的所有边，保留在网络图中，边权为 $+ \infty$ 。

答案为：原图所有正权点之和减去网络图的最小割.

在网络图上，如果割掉了 $S$ 到某个正权点的边，代表不选这个实验项目；如果割掉了负权点到 $T$ 的边，代表选这个实验仪器。而对于原图的边，由于流量为 $+ \infty$ ，所以一定不会割这个点。（可以独立思考一下为什么这样是对的）

根据最小割最大流定理，可以轻易求出答案。

总结

对于最大权闭合子图问题，可以作出一个总结：

先将问题转化成一个形如：每个点有正负点权，选这个点就一定要选某些点。求最大点权和（或最小，只需将边权取负就行了）

接着建模：将正权边与 $S$ 连接，流量为权值；将负权边与 $T$ 连接，流量为权值相反数。

跑 Dinic，答案是：所有正权点点权和减去最小割。

练习题

P4313 文理分科

首先仔细思考一下发现不能把一个学生拆成 art 和 science 两个点。于是考虑先钦定所有学生是 art，再考虑将它改成 science 对答案的贡献。

从 art 改成 science 对答案的影响有（下面用数组的简称）：

答案加上 $s_{i, j} - a_{i, j}$ 。
如果旁边全是 art，则答案减去 $sa_{i, j}$ 。
如果旁边全是 science，则答案加上 $ss_{i, j}$ 。

这样就可以将这三种贡献抽象成 $3$ 类点：

学生从 art 改成 science，点权是 $s_{i, j} - a_{i, j}$ 。
一个学生和相邻的学生有一个不选 art，点权是 $-sa_{i, j}$ 。
一个学生和相邻的学生全部都!选 science，点权是 $ss_{i, j}$ 。

这 $3$ 类点的关系是：

选择了 $1$ 类点就要选择它相邻的 $2$ 类点。
选择了 $3$ 类点就要选择它相邻的 $1$ 类点。

于是一个最大权闭合子图问题就产生了，使用最小割不难解决此题，注意建边时要对 $s_{i, j} - a_{i, j}$ 的正负性讨论一下，不能建出流量为负的边。

P2805 [NOI2009] 植物大战僵尸：

比较板，注意互相保护的植物不要加进网络图里面，可以先拓扑一遍找到互相保护的植物。

[国家集训队] happiness

和文理分科几乎一模一样，有五类点：

学生从 art 变成 science。
上下不同时选 art。
上下同时选 science。
左右不同时选 art。
左右同时选 science。

然后直接最小割就行了。

最小费用最大流

模板

同样没什么好说的，代码：

struct flow {
  int S, T, head[N], cur[N], nex[M << 1], tot = 1, dep[N];
  i64 h[N], d[N];
  bool vis[N];
  struct E {int to, nxt, flow, cost;} edge[M << 1];
  void ad(int x, int y, int z, int w) {
    edge[++tot] = (E) {x, y, z, w};
    nex[tot] = head[x]; head[x] = tot;
  }
  void add(int x, int y, int z, int w) {
    ad(x, y, z, w);
    ad(y, x, 0, -w);
  }
  void spfa() {
    queue <int> q;
    fill(h + 1, h + 1 + n, 1E15);
    q.emplace(S); h[S] = 0;
    while (!q.empty()) {
      int u = q.front(); q.pop(); vis[u] = 0;
      for (int i = head[u]; i; i = nex[i]) {
        int v = edge[i].nxt, w = edge[i].flow, c = edge[i].cost;
        if (w > 0 && h[v] > h[u] + c) {
          h[v] = h[u] + c;
          if (!vis[v]) q.emplace(v), vis[v] = 1;
        }
      }
    }
  }
  bool dijkstra() {
    fill(dep + 1, dep + 1 + n, 0);
    fill(d + 1, d + 1 + n, 1E15);
    fill(vis + 1, vis + 1 + n, 0);
    priority_queue <pair <i64, int>> q; 
    dep[S] = 1; d[S] = 0; q.emplace(make_pair(0, S));
    while (!q.empty()) {
      int u = q.top().second; q.pop();
      for (int i = head[u]; i; i = nex[i]) {
        int v = edge[i].nxt, w = edge[i].flow, c = edge[i].cost;
        if (w > 0 && d[v] > d[u] + c + h[u] - h[v]) {
          d[v] = d[u] + h[u] - h[v] + c;
          dep[v] = dep[u] + 1;
          q.emplace(make_pair(-d[v], v));
        }
      }
    } return d[T] < 1E15;
  }
  i64 cost;
  int dfs(int u, int flow) {
    if (u == T || !flow) return flow;
    vis[u] = 1;
    int res = 0;
    for (int &i = cur[u]; res < flow && i; i = nex[i]) {
      int v = edge[i].nxt, w = edge[i].flow, c = edge[i].cost;
      if (!vis[v] && dep[v] == dep[u] + 1 && d[v] == d[u] + c + h[u] - h[v] && w > 0) {
        int k = dfs(v, min(flow - res, w));
        if (!k) vis[v] = 1;
        else {
          edge[i].flow -= k;
          edge[i ^ 1].flow += k;
          res += k;
          cost += 1LL * k * c;
        }
      }
    } vis[u] = 0; return res;
  }
  i64 dinic() {
    i64 ans = 0;
    spfa();
    while (dijkstra()) {
      fill(vis + 1, vis + 1 + n, 0);
      copy(head + 1, head + 1 + n, cur + 1);
      ans += dfs(S, INT_MAX);
    } return ans;
  }
} dc;
// 这个是加了一些优化的，在某些题目中可能不适用。