【图论】网络流

算法进阶课网络流部分总结

基本概念

流网络

由点集和边集组成的有向图，其中包含一个源点 s 和一个汇点 t，边上的权值表示

可以将其理解为水流和管道，从源点流出水流，流入汇点，边上的权值表示管道可以流过的水量

可行流

满足以下条件的叫做可行流：

• 容量限制：一条边上流过的流量不能超过其最大限制，即 $0\le f(u,v)\le c(u,v)$
• 流量守恒：流入每个点的流量等于流出该点的流量，即 $\sum f(v,x)=\sum f(x,v)$

$|f|$：从源点流向汇点的流量值，有 $|f|=f(s,v)-f(v,s)$

最大流

最大流，全称最大可行流，即流量值最大的可行流

残留网络

残留网络 $G_f$ 是针对某一条可行流而言的，可行流不同，残留网络也不同

残留网络中：

• 点集和原图里所有边一样
• 边集：
  • 包含原来的所有边，这些边的容量定义为原容量减去流量（也就是还可以流过的流量）
  • 包含原边的所有反向边，这些边的容量定义为原来的流量（可以理解为能退回去的流量）

定理

可行流 $f$ 的残留网络定义为 $f^{\prime }$，有这样的关系：$f+f^{\prime }$ 也是原网络的一个可行流，且流量等于 $|f|+|f^{\prime }|$

其中 $f+f^{\prime }$ 意为同一条边的流量，方向相同就相加，方向不同就减去

增广路径

增广路径指：在残留网络里，从源点出发，沿着流量大于 0 的边，如果能走到汇点，这条路径称为增广路径

增广路径一定是可行流，流量一定大于 0

也就是在残留网络取一个流量大于 0 的可行流

没有增广路，就可以断定当前的可行流是最大流

割

定义：对于流网络 $G=(V,E)$，将点集 $V$ 不重不漏分成两个子集 $S,T$，使得源点 s 在 $S$ 中，汇点 t 在 $T$ 中

容量：所有从 $S$ 指向 $T$ 的边的容量之和 （不算从 $T$ 指向 $S$ 的边）

流量：所有从 $S$ 指向 $T$ 的边的流量之和 - 所有从 $T$ 指向 $S$ 的边的流量之和

$f(X,Y)$：从 X 流向 Y 的净流量（等于从X流向Y的流量减去从Y流向X的流量）

$f(X,Y)={\sum }_{u\in X}{\sum }_{v\in Y}f(u,v)-{\sum }_{u\in X}{\sum }_{v\in Y}f(v,u)$

有：

$f(X,Y)=-f(Y,X)$

$f(X,X)=0$

$f(Z,X\cup Y)=f(Z,X)+f(Z,Y)$

性质

1. 对于任意的割，割的流量 < 割的容量
2. 对于任意的割和可行流，割的流量 = 可行流的流量
3. 对于任意的割和可行流，可行流的流量 < 割的容量

最小割

最小割：最小容量割

最大流最小割定理

对于某一个流网络 G 来说，以下三个条件可以相互等价：

• 一个可行流 $f$ 是最大可行流
• 可行流 $f$ 的残留网络中不存在增广路
• 存在一个割 $[S,T]$ 使得可行流的流量等于割的容量

最大流等于最小割

算法

思想：维护残留网络，在残留网络里不断找增广路，将增广路删去，一直重复直到找不到增广路为止

EK算法

时间复杂度：$O(n{m}^2)$

步骤：

1. 找增广路
2. 更新残留网络（正向边容量 - 流量，反向边容量 + 流量）

$code$

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int d[N], pre[N]; // d[i]:从起点走到某个点的这条路径上的容量最小值 pre[i]:一条增广路径的前缀边void add(int a, int b, int c)
{e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}bool bfs()
{queue<int> q;vector<bool> st(n + 1);q.push(S), st[S] = true, d[S] = INF;while (q.size()){int t = q.front();q.pop();for (int i = h[t]; i != -1; i = ne[i]){int ver = e[i];if (!st[ver] && f[i]) // ver没访问过且容量剩余{st[ver] = true;d[ver] = min(d[t], f[i]);pre[ver] = i;if (ver == T) return true;q.push(ver);}}}return false;
}int EK()
{int r = 0; // 流过的流量while (bfs()){r += d[T];for (int i = T; i != S; i = e[pre[i] ^ 1])f[pre[i]] -= d[T], f[pre[i] ^ 1] += d[T];}return r;
}void solve()
{cin >> n >> m >> S >> T;for (int i = 1; i <= n; i ++ ) h[i] = -1;while (m -- ){int a, b, c;cin >> a >> b >> c;add(a, b, c);}cout << EK() << '\n';
}

Dinic算法

时间复杂度：$O(n^{2}m)$

EK算法是每次只增广一条路径，而Dinic算法是每次增广尽可能多的路径

通过bfs完成建图和分层两个操作，然后dfs直到没有增广路为止

优化：

• 当前弧优化：使用 cur 数组，标记每个结点当前遍历到哪条边了，之前遍历过的已经用完了，所以从 cur[i] 开始遍历，防止重复

$code$

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int d[N], pre[N], cur[N]; // d[i]:每个点的层数，源点为0 pre[i]:一条增广路径的前缀边 cur[i]:当前弧优化void add(int a, int b, int c)
{e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}bool bfs()
{queue<int> q;for (int i = 1; i <= n; i ++ ) d[i] = -1;q.push(S), d[S] = 0, cur[S] = h[S]; // 初始化while (q.size()){auto t = q.front();q.pop();for (int i = h[t]; i != -1; i = ne[i]){int ver = e[i];if (d[ver] == -1 && f[i]) // 这个点没访问过且连边还有容量{d[ver] = d[t] + 1; // 更新该点层数cur[ver] = h[ver]; // 当前弧优化if (ver == T) return true; // 遇到汇点q.push(ver);}}}return false; // 没有增广路
}int find(int u, int limit) // u是当前点 limit是流入这个点的流量 函数返回从这个点最多能流出的流量
{if (u == T) return limit;int flow = 0; // 从当前点流出的最大流量for (int i = cur[u]; i != -1 && flow < limit; i = ne[i]){cur[u] = i; // 当前弧优化 能访问到第i条边说明第i条边之前的边都已经不能用了int ver = e[i];if (d[ver] == d[u] + 1 && f[i]){int t = find(ver, min(f[i], limit-  flow));if (!t) d[ver] = -1; // 没有流量流出 说明这个点已经废了else f[i] -= t, f[i ^ 1] += t, flow += t;}}return flow;
}int dinic()
{int r = 0, flow;while (bfs())while (flow = find(S, INF))r += flow;return r;
}void solve()
{cin >> n >> m >> S >> T;for (int i = 1; i <= n; i ++ ) h[i] = -1;while (m -- ){int a, b, c;cin >> a >> b >> c;add(a, b, c);}cout << dinic() << '\n';
}

最大流模型

基本思想

问题 $P$ 的所有解决方案为集合 $S$，最大流的所有可行流为集合 $f$，$S$ 和 $f$ 必须是一一对应的关系

二分图匹配

P2756 飞行员配对方案问题

题目链接

题意是有两堆点，特定的两点之间可以进行匹配，问最大匹配数

很显然是个二分图匹配问题，可以用匈牙利算法解决，但利用dinic可以将复杂度降到 $O(n\sqrt{m})$

我们将源点连向第一堆点，将第二堆点连向汇点，合法的匹配方案即转化为两堆点之间的连边，容量均为1，求最大流即可

void solve()
{cin >> m >> n;S = n + 1, T = n + 2;for (int i = 1; i <= n + 2; i ++ ) h[i] = -1;for (int i = 1; i <= m; i ++ ) add(S, i, 1);for (int i = m + 1; i <= n; i ++ ) add(i, T, 1);int a, b;cin >> a >> b;while (a != -1 && b != -1){add(a, b, 1);cin >> a >> b;}cout << dinic() << '\n';for (int i = 0; i < idx; i += 2){if (e[i] > m && e[i] <= n && !f[i]){cout << e[i ^ 1] << ' ' << e[i] << '\n';}}
}

P3254 圆桌问题

题目链接

题意是，有 m 个单位和 n 张桌子，告诉你每个单位的人数和每张桌子的人数，同一个单位的人不能坐同一张桌子，问是否有合法分配方案

又是匹配问题，我们将 m 个单位和 n 张桌子分别看成两堆点

• 单位 $a$ 向桌子 $b$ 连一条容量为 1 的边意为 $a$ 单位派了一个人去桌子 $b$
• 源点向单位 $a$ 连一条容量为 $c$ 的边表示单位 $a$ 派了 $c$ 个人参加
• 桌子 $b$ 向汇点连了一条容量为 $c$ 的边表示桌子 $b$ 能坐 $c$ 个人

求得的最大流就是参加的人数，如果等于总人数的话，说明有这样一种匹配方案

void solve()
{cin >> m >> n;for (int i = 1; i <= n + m + 2; i ++ ) h[i] = -1;S = n + m + 1, T = n + m + 2;vector<int> r(m + 1), c(n + 1);int sum = 0;for (int i = 1; i <= m; i ++ ){cin >> r[i];sum += r[i];}for (int i = 1; i <= n; i ++ ) cin >> c[i];for (int i = 1; i <= m; i ++ ) add(S, i, r[i]);for (int i = m + 1; i <= n + m; i ++ ) add(i, T, c[i - m]);for (int i = 1; i <= m; i ++ ){for (int j = m + 1; j <= n + m; j ++ ){add(i, j, 1);}}if (dinic() != sum){cout << 0 << '\n';return;}cout << 1 << '\n';for (int i = 1; i <= m; i ++ ){for (int j = h[i]; j != -1; j = ne[j]){if (f[j]) continue;int v = e[j];cout << v - m << ' ';}cout << '\n';}
}

上下界可行流

无源汇上下界可行流

给每条边规定的容量限制为 $c_l(u,v)\le f(u,v)\le c_u(u,v)$

怎么对其进行转换，使得能满足 $f(u,v)\le c$ 的形式呢？

很显然，同减 $c_l(u,v)$ 就可以了

于是限制变成 $0\le f(u,v)-c_l(u,v)\le c_u(u,v)-c_l(u,v)$

也就是，我们将每一条边的流量减去 $c_l(u,v)$，容量变为上界减下界，这显然是满足容量限制的

那满不满足流量守恒呢，不一定

设少进入点 $x$ 的流量 $c_{入}$，少流出点 $x$ 的流量 $c_{出}$，点 $x$ 就少流入了 $c_{入}-c_{出}$，怎么处理这个少流入的流量呢，我们连一条边从源点到 $x$，流量是 $c_{入}-c_{出}$ 就可以了（如果少流出了，就连一条 $x$ 到汇点的边，道理是一样的）

模板题链接

void add(int a, int b, int c, int d)
{e[idx] = b, f[idx] = d - c, l[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}void solve()
{cin >> n >> m;S = n + 1, T = n + 2;for (int i = 1; i <= n + 2; i ++ ) h[i] = -1;for (int i = 0; i < m; i ++ ){int a, b, c, d;cin >> a >> b >> c >> d;add(a, b, c, d);A[a] -= c, A[b] += c;}int tot = 0;for (int i = 1; i <= n; i ++ ){if (A[i] > 0) add(S, i, 0, A[i]), tot += A[i];else if (A[i] < 0) add(i, T, 0, -A[i]);}if (dinic() != tot){cout << "NO\n";return;}cout << "YES\n";for (int i = 0; i < m * 2; i += 2){cout << f[i ^ 1] + l[i] << '\n';}
}

有源汇上下界可行流

有源汇和无源汇的区别就是，无源汇流网络中，所有点都是满足流量守恒的，而有源汇流网络中，源点和汇点是不满足流量守恒的

于是我们可以将有源汇流网络变成无源汇流网络，也就是让源点和汇点也满足流量守恒，之后根据无源汇上下界可行流的方法去做

怎么让源点和汇点也满足流量守恒？直接连一条从汇点指向源点的边，容量为 $INF$ 即可

有源汇上下界最大流

模板题链接

我们先将问题转换成有源汇上下界最大流，这个时候，我们已经在原图的基础上，进行了以下操作（设原图中给定的源点和汇点分别用 $s$ 和 $t$ 表示）：

• 连了一条由 $t$ 指向 $s$ 的边，容量为 $INF$
• 创建虚拟源点 $S$，弥补每个点少流入的流量
• 创建虚拟源点 $T$，处理每个点多流出的流量

先跑一遍dinic，通过看从 $S$ 点流出的流量是否等于 $T$ 点流出的流量来判断是否存在这样的上下界可行流，如果不存在这样的方案就不用谈什么最大流了

此时，由于虚拟源点和虚拟汇点的特殊作用，与它们相连的边都是满流，不可能再被用到，也就是说不可能对之后的最大流造成任何贡献，所以我们直接把这些边删去（可以直接将 $S$ 和 $T$ 更新为原图的 $s$ 和 $t$），同时，由 $t$ 指向 $s$ 的那条边也是满流，直接删去（可以将 f[idx - 1] 和 f[idx - 2] 直接置为 0），之后再跑一遍最大流，两次叠加的结果即为最终的最大流

void solve()
{int s, t;cin >> n >> m >> s >> t;S = n + 1, T = n + 2;for (int i = 1; i <= n + 2; i ++ ) h[i] = -1;for (int i = 0; i < m; i ++ ){int a, b, c, d;cin >> a >> b >> c >> d;add(a, b, c, d);A[a] -= c, A[b] += c;}int tot = 0;for (int i = 1; i <= n; i ++ ){if (A[i] > 0) add(S, i, 0, A[i]), tot += A[i];else if (A[i] < 0) add(i, T, 0, -A[i]);}add(t, s, 0, INF);if (dinic() != tot){cout << "please go home to sleep\n";return;}int res = f[idx - 1]; // 原图中s到t的最大流S = s, T = t;f[idx - 2] = f[idx - 1] = 0; // 把新加的从t指向s的边删掉cout << res + dinic() << '\n';
}

有源汇上下界最小流

反过来想，因为从源点到汇点的最大流等于从汇点到源点的流量的相反数，所以想求最小流，只需要求汇点到源点的最大流就可以了

所以一开始还是按之前的方式创建虚拟源点汇点求可行流，第二次dinic的时候将 $t$ 标记为源点，$s$ 标记为汇点，答案是第一次的流量减第二次的流量

模板题链接

void solve()
{int s, t;cin >> n >> m >> s >> t;S = n + 1, T = n + 2;for (int i = 1; i <= n + 2; i ++ ) h[i] = -1;for (int i = 0; i < m; i ++ ){int a, b, c, d;cin >> a >> b >> c >> d;add(a, b, c, d);A[a] -= c, A[b] += c;}int tot = 0;for (int i = 1; i <= n; i ++ ){if (A[i] > 0) add(S, i, 0, A[i]), tot += A[i];else if (A[i] < 0) add(i, T, 0, -A[i]);}add(t, s, 0, INF);if (dinic() != tot){cout << "please go home to sleep\n";return;}int res = f[idx - 1]; // 原图中s到t的最大流S = t, T = s;f[idx - 2] = f[idx - 1] = 0; // 把新加的从t指向s的边删掉cout << res - dinic() << '\n';
}

多源汇最大流

很显然是虚拟源点和虚拟汇点的思路

void solve()
{int sc, tc;cin >> n >> m >> sc >> tc;S = n + 1, T = n + 2;for (int i = 1; i <= n + 2; i ++ ) h[i] = -1;for (int i = 0; i < sc; i ++ ) // 将虚拟源点和原题源点连边{int x; cin >> x;add(S, x, INF);}for (int i = 0; i < tc; i ++ ) // 将虚拟汇点和原题汇点连边{int x; cin >> x;add(x, T, INF);}for (int i = 0; i < m; i ++ ){int a, b, c;cin >> a >> b >> c;add(a, b, c);}cout << dinic() << '\n';
}

关键边

题目链接

题意是给你一个 $n$ 个点，$m$ 条边的流网络，每条边有最大容量限制，问能不能增加一条边的容量使得最大流增加，输出这样的边有多少条

画图即可知道，这样的边有个条件就是一定是流量等于容量，如果流量小于容量，说明在前面的边里对其有流量限制，尽管加这条边的容量也没办法让它多流

另外如果没有多余流量可以流的话，光加容量也没用，所以判断一下源点和汇点能否到达当前边的两个端点，能的话当前边即为符合条件的边

bool st_s[N], st_t[N];void dfs_r(int u, bool st[], int t)
{st[u] = true;for (int i = h[u]; i != -1; i = ne[i]){int j = i ^ t;int v = e[i];if (f[j] && !st[v]) dfs_r(v, st, t);}
}void solve()
{cin >> n >> m;S = 0, T = n - 1;for (int i = 0; i <= n - 1; i ++ ) h[i] = -1;for (int i = 0; i < m; i ++ ){int a, b, c;cin >> a >> b >> c;add(a, b, c);}dinic();dfs_r(S, st_s, 0);dfs_r(T, st_t, 1);int ans = 0;for (int i = 0; i < m * 2; i += 2){int v1 = e[i], v2 = e[i ^ 1];if (!f[i] && st_s[v2] && st_t[v1]) ans ++ ;}cout << ans << '\n';
}

最大流判定

P1674 [USACO05FEB] Secret Milking Machine G （二分）

题目链接

题意是给出一个流网络，判断从 1 号点到 n 号点是否存在 t 条相互之间没有公共边的可行流，输出最长道路的最小长度

首先，如果我们不看最长道路的最小长度这个限制，如何计算从 1 号点到 n 号点存在多少条没有公共边的可行流呢？只需要根据所给条件建图，然后每条边的容量为1就可以了

现在问我们最小长度，很容易发现这个问题是具有二段性的，所以二分去做，符合条件的边容量为 1，不符合的容量为 0

void solve()
{cin >> n >> m >> K;S = 1, T = n;for (int i = 1; i <= n; i ++ ) h[i] = -1;for (int i = 0; i < m; i ++ ){int a, b, c;cin >> a >> b >> c;add(a, b, c);}int l = 0, r = 1e6;auto check = [&](int mid){for (int i = 0; i < idx; i ++ ){if (w[i] <= mid) f[i] = 1;else f[i] = 0;}if (dinic() >= K) return true;else return false;};while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}cout << r << '\n';
}

P2754 [CTSC1999] 家园 / 星际转移问题（分层图）

题意是给出几个太空站和太空飞船，飞船可以顺次经过一些太空站，每次能载的人数有限，一共有 $k$ 个人，问所有人从 0 号点到 n + 1 号点的最少天数

很经典的建图方式，值得学习一下

首先并查集判断起点终点是否连通

把 $n$ 个太空站看做点，太空飞船看做边，对于每一天，我们都建 $n+1$ 个太空站（还要包括终点，所以多1），然后这样建边：

• 首先，源点 $S$ 向第一天的 $0$ 号点建一条容量为 $k$ 的边
• 每一天的终点 $n+1$ 向汇点 $T$ 建一条容量为 $INF$ 的边
• 对于第 $i$ 天的第 $j$ 个点来说，第 $i-1$ 天到达第 $j$ 个点的人可以停在这个点不动，所以连一条从第 $i-1$ 天的第 $j$ 个点向第 $i$ 天的第 $j$ 个点的边
• 对于第 $i$ 个飞船来说，下一天会到达下一个太空站，所以连一条前一天所到达太空站向下一天所到达太空站的边

之后从小到大枚举天数（这里为什么不使用二分呢？因为天数越少，我们需要的点数越少），判断是否满足条件即可

struct Ship {int h, r, id[30];
} ship[30];int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}int get(int id, int day)
{return day * (n + 2) + id;
}void solve()
{cin >> n >> m >> k;S = N - 2, T = N - 1;for (int i = 0; i < N; i ++ ) h[i] = -1;for (int i = 0; i < 30; i ++ ) p[i] = i;for (int i = 0; i < m; i ++ ){int a, b;cin >> a >> b;ship[i] = {a, b};for (int j = 0; j < b; j ++ ){int id; cin >> id;if (id == -1) id = n + 1;ship[i].id[j] = id;if (j){int x = ship[i].id[j - 1];p[find(x)] = find(id);}}}if (find(0) != find(n + 1)) cout << 0 << '\n';else{add(S, get(0, 0), k);add(get(n + 1, 0), T, INF);int day = 1, res = 0;while (1){add(get(n + 1, day), T, INF);for (int i = 0; i <= n + 1; i ++ ) add(get(i, day - 1), get(i, day), INF);for (int i = 0; i < m; i ++ ){int r = ship[i].r;int a = ship[i].id[(day - 1) % r], b = ship[i].id[day % r];add(get(a, day - 1), get(b, day), ship[i].h);}res += dinic();if (res >= k) break;day ++ ;}cout << day << '\n';}
}

拆点

P2891 [USACO07OPEN] Dining G

题目链接

题意是给出所有牛和每一头牛喜欢的食物和饮料，现在要给每一头牛分配一个食物和一个饮料，问最多有多少匹配

这一题乍一看像是二分图匹配，于是我们仿照二分图的建图方式，源点向所有食物连一条容量为 1 的边，所有饮料向汇点连一条容量为 1 的边，然后根据牛的喜好来连牛和食物、饮料的边

但是这样真的正确吗？我们看下面这张图：

这张图里最大流是 2，但是我们只有一头牛，为什么会有 2 的流量呢，因为我们两组食物和饮料共用了一头牛，这在题目中是被禁止的，那我们怎么防止这种情况发生呢？

拆点，将每一头牛从一个点拆成两个点（入点和出点），从入点向出点连一条容量为 1 的边，就可以控制每一头牛只匹配一对食物和饮料了

void solve()
{cin >> n >> F >> D;for (int i = 0; i < N; i ++ ) h[i] = -1;S = N - 2, T = N - 1;for (int i = 1; i <= F; i ++ ) add(S, i, 1);for (int i = F + 1; i <= F + D; i ++ ) add(i, T, 1);for (int i = 1; i <= n; i ++ ){int c1, c2; cin >> c1 >> c2;for (int j = 0; j < c1; j ++ ){int x; cin >> x;add(x, F + D + (i - 1) * 2 + 1, 1);}for (int j = 0; j < c2; j ++ ){int x; cin >> x;add(F + D + (i - 1) * 2 + 2, x + F, 1);}add(F + D + (i - 1) * 2 + 1, F + D + (i - 1) * 2 + 2, 1);}cout << dinic() << '\n';
}

P2766 最长不下降子序列问题

题目链接

题意是给出一个序列，回答三个问题：

1. 最长不下降子序列的元素个数 $s$
2. 长度为 $s$ 且不共用元素的最长不下降子序列个数
3. 可以多次使用 $a_1$ 和 $a_n$ 的最长不下降子序列个数

首先第一个问题，用动态规划解决即可

第二和第三个问题需要建图，每个元素看做一个点，如果 $dp[i]=dp[j]+1$（表示可以从第 $j$ 个点转移到第 $i$ 个点），那么就从第 $j$ 个点向第 $i$ 个点连一条容量是 1 的边

第三个问题，只需要把从源点向第 1 个点连的边和从最后一个点向汇点连的边容量置为 $INF$ 即可

怎么处理每个点只能用一次呢？和上一题一样，把每个点拆成入点和出点，连一条容量为 1 的边即可

同时需要注意特判，如果最长不下降子序列的长度为 1，后两个问题直接输出 $n$ 即可

void solve()
{cin >> n;for (int i = 0; i < N; i ++ ) h[i] = -1;for (int i = 1; i <= n; i ++ ) cin >> w[i];S = n * 2 + 1, T = n * 2 + 2;int s = 0;for (int i = 1; i <= n; i ++ ){dp[i] = 1;for (int j = 1; j < i; j ++ )if (w[i] >= w[j])dp[i] = max(dp[j] + 1, dp[i]);s = max(s, dp[i]);add(i, i + n, 1);if (dp[i] == 1) add(S, i, 1);}for (int i = 1; i <= n; i ++ ){for (int j = 1; j < i; j ++ )if (w[i] >= w[j] && dp[i] == dp[j] + 1) add(j + n, i, 1);if (dp[i] == s) add(i + n, T, 1);}cout << s << '\n';if (s == 1) cout << n << '\n' << n << '\n';else{int res = dinic();cout << res << '\n';for (int i = 0; i < idx; i += 2){int a = e[i ^ 1], b = e[i];if (a == S && b == 1) f[i] = INF;else if (a == 1 && b == 1 + n) f[i] = INF;else if (a == n && b == n + n) f[i] = INF;else if (a == n + n && b == T) f[i] = INF;}cout << res + dinic() << '\n';}
}

最小割模型

直接应用

网络战争（01分数规划）

题目给出一个 $n$ 个点 $m$ 条边的带权无向图，求将源点 $S$ 和汇点 $T$ 分开的边割集 $C$，使得 $\frac{{\sum }_{e\in C}{w}_e}{|C|}$ 最小，输出这个最小值

所有求形如 $\frac{{\sum }_{e\in C}{w}_e}{|C|}$ 的最值问题，都可以考虑转化成 01分数规划

设 $\frac{{\sum }_{e\in C}{w}_e}{|C|}>\lambda$，有 ${\sum }_{e\in C}{w}_e>\lambda |C|$，又可推 ${\sum }_{e\in C}{w}_e-\lambda |C|>0$，由于 ${\sum }_{e\in C}{w}_e$ 也是由 $|C|$ 个元素组成，所以可以化简为 $\sum (w-\lambda )>0$，换成小于号仍然成立，发现其具有二段性，于是我们可以通过二分来解决这题

首先将原图中所有边的容量减去 $\lambda$，如果新的容量小于等于 0，那最终的边割集一定包含这条边，因为它会让最终答案更小

对于其余边，除了选择两个点集之间的边以外，还可以选择点集之内的边，但是选这些边显然只会增加所求值，所以这些边一定不会选到，因此只需要取最小割就可以了，于是最终答案就是边权为负的这些边加上最小割的边，由于最大流等于最小割，所以直接跑最大流就可以了

double work(double mid)
{double res = 0;for (int i = 0; i < idx; i += 2){if (w[i] <= mid){res += w[i] - mid;f[i] = f[i ^ 1] = 0;}else f[i] = f[i ^ 1] = w[i] - mid;}res += dinic();return res;
}void solve()
{cin >> n >> m >> S >> T;for (int i = 1; i <= n; i ++ ) h[i] = -1;for (int i = 0; i < m; i ++ ){int a, b, c;cin >> a >> b >> c;add(a, b, c);}double l = 0, r = 1e7;while (r - l > eps){double mid = (l + r) / 2;if (work(mid) < 0) r = mid;else l = mid;}printf("%.2lf\n", r);
}

最优标号

题意是给你一个无向图，每个点都有一个标号 $p$，对于某条边，定义其费用为 $cost(u,v)=p[u]\stackrel{ˆ}{}p[v]$，现在已知部分点的标号，需要确定剩余点标号使所有边的费用和最小

按位考虑，如果当前考虑第 $k$ 位，由于每一位只有 0 和 1 两种选择，所以我们可以将点分为两个集合，这一位对于答案的贡献可以转化为这两个集合之间有多少条边，即最小割模型

定义虚拟源点和虚拟汇点，源点在第一个集合，汇点在第二个集合，如果结点一开始就有编号，若编号在这一位上是 0 ，就连一条从源点到该点、容量为正无穷的边（保证求最小割不会选到这一条边），若编号在这一位上是 1，就连一条从该点到汇点，容量为正无穷的边（保证求最小割不会选到这一条边），其余边容量均为 1，之后求最小割计算每位贡献即可

int build(int pos)
{for (int i = 1; i <= n + 2; i ++ ) h[i] = -1;idx = 0;for (int i = 0; i < m; i ++ ) add(edge[i].first, edge[i].second, 1, 1);for (int i = 1; i <= n; i ++ ){if (pi[i] == -1) continue;else if ((pi[i] >> pos) & 1) add(i, T, INF, 0);else add(S, i, INF, 0);}int res = dinic();return (res << pos);
}void solve()
{cin >> n >> m;S = n + 1, T = n + 2;for (int i = 1; i <= n + 2; i ++ ) pi[i] = -1;for (int i = 0; i < m; i ++ ) cin >> edge[i].first >> edge[i].second;int k; cin >> k;for (int i = 0; i < k; i ++ ){int u, x;cin >> u >> x;pi[u] = x;}int res = 0;for (int i = 0; i < 31; i ++ ) res += build(i);cout << res << '\n';
}

最大权闭合子图

闭合子图：给定一个有向图 $G=(V,E)$，图中的某一点集需要满足，点集内部的所有边，不能从点集内指向点集外，只能在内部消化，点集加上相关的边称为一个闭合子图

（只需要保证边不从里面指向外面即可，可以从外面指向里面）

最大权闭合子图是指权值最大的闭合子图（权值是每个点上的权值）

构造方式：原有向图 $G=(V,E)$，流网络 $N=(V_N,E_N)$，构造出的流网络：

• 点：原图中的点+源点+汇点
• 边：原图中的边（容量为 $INF$）+源点向权值为正数的点连边（容量为权值）+权值为负数的点向汇点连边（容量为权值的相反数）

解决问题的大体思路就是将原问题的闭合子图对应到割

在这个问题中，简单割代表割中的边要么和源点相连，要么和汇点相连，不存在既不和源点连也不和汇点连的边

最小割一定是一个简单割（因为最小割的容量是有限值，如果包括了中间不和源点汇点相连的边，容量就不是有限值了）

原问题的闭合子图可以和流网络的简单割一一对应，求闭合子图的最值，只需要求简单割的最值，又因为最小割一定是简单割，最小割的最值一定是简单割的最值，所以只需要求出所有割的最值（即为最小割），就是闭合子图的最值了

设闭合子图中点集为 $V_1$，其余点为 $V_2$，只会存在 $V_1$ 向汇点 $t$ 连的边和源点 $s$ 向 $V_2$ 连的边，有 $C[S,T]=C[V_1,t]+C[s,V_2]={\sum }_{v\in V_2^{+}}{w}_v+{\sum }_{v\in V_1^{-}}{w}_v$

$V_1$ 的总权值 $w(V_1)={\sum }_{v\in V_1^{+}}{w}_v-{\sum }_{v\in V_2^{+}}{w}_v$

两式相加，$C[S,T]+w(V_1)=w(V^{+})$

$w(V^{+})$ 是定值，想让 $w(V_1)$ 最大，就让 $C[S,T]$ 最小，即求流网络的最小割，最大流

$w(V_1)=w(V^{+})-C[S,T]$

P4174 [NOI2006] 最大获利

题目链接

题意是有 $n$ 个地方可以建基站，在第 $i$ 个地方建基站的花费是 $p_i$，有 $m$ 个用户群，第 $i$ 个用户群所对应的利益是 $c_i$，每个用户群对应两个基站，只有这两个基站都建立了才能获得该用户群对应的利益，问如何建立基站才能使得获益最大，获益为从用户群获得的利益减去建基站的花费

我们将基站和用户群都看做点，基站的点权为 $-p_i$，用户群的点权为 $c_i$，这样问题就变成了我们选择用户群和基站，使得选择的用户群对应的基站都被选择了，要使选择的所有点权值之和最大

怎么让选择的用户群对应的基站都被选择呢，我们从用户群向对应的基站连一条有向边，这样就变成了找到有向图的最大权闭合子图了

void solve()
{cin >> n >> m;S = n + m + 1, T = n + m + 2;for (int i = 1; i < N; i ++ ) h[i] = -1;for (int i = 1; i <= n; i ++ ){int x; cin >> x;add(i, T, x, 0);}int ans = 0;for (int i = 1; i <= m; i ++ ){int a, b, c; cin >> a >> b >> c;add(n + i, a, INF, 0);add(n + i, b, INF, 0);add(S, n + i, c, 0);ans += c;}cout << ans - dinic() << '\n';
}

最大密度子图

在原图 $G=(V,E)$ 的基础上选择一个点集 $V^{\prime }$ 和一个边集 $E^{\prime }$，使得边集中每一条边的两个端点，都出现在点集内

最大密度子图：在以上的所有选择方案种，$\frac{|E^{\prime }|}{|V^{\prime }|}$ 最大的图

最大化一个分式，想到 01分数规划+二分：

设 $\frac{|E^{\prime }|}{|V^{\prime }|}=g$，则有 $|E^{\prime }|-g|V^{\prime }|=0$，如果 $|E^{\prime }|-g|V^{\prime }|$ 的最大值大于 $0$，说明 $g$ 小了，反之同理

所以核心就是最大化 $|E^{\prime }|-g|V^{\prime }|$，也就是最小化 $g|V^{\prime }|-|E^{\prime }|$，这个式子又可以化简为 ${\sum }_{v\in V}g-(\frac{{\sum }_{v\in V^{\prime }}{d}_v}{2}-\frac{C[V^{\prime },\overline{V^{\prime }}]}{2})$ ，怎么理解这个化简呢，减号前面很好理解，减号后面也就是边数，我们可以把所有边一分为二，两个部分分别给两个端点，边数也就是度数除以 $2$，然后再减去割边，得到子图中的边数，整理一下式子： $\frac{1}{2}\times ({\sum }_{v\in V^{\prime }}(2g-d_v)+C[V^{\prime },\overline{V^{\prime }}])$到这就将原问题和最小割关联起来了

最大密度子图问题也可以转化为最大权闭合子图问题，只需要将点看成点，边也看成点，边的点权值是 $1$，点的点权值是 $-g$，边 $(u,v)$ 就让这条边形成的点向 $u$ 和 $v$ 连有向边

费用流模型

定义

费用流：所有最大可行流中，费用的最小 / 最大值

费用：可行流中用到的边的费用乘流量之和

如果一张图有最大流，一定有最小费用最大流（但是不一定能求出来）

求法 - 基于EK算法

把EK算法中的bfs换成spfa即可

特别地，常规的最小费用最大流算法不能处理负权回路问题

从 $u$ 到 $v$ 费用记作 $w(u,v)$，那么 $w(v,u)=-w(u,v)$

步骤：

1. 找一条增广路（使用spfa找一条从源点到汇点的最短/长路）
2. 更新当前可行流

模板 - zkw费用流

据说跑起来很快

最小/大费用最大流

class Graph
{
public:int n, m;int top, to[M << 1], fw[M << 1], ct[M << 1];vector<int> g[V];Graph() { top = 1; }void add(int x, int y, int f, int c){g[x].push_back(++top);to[top] = y, fw[top] = f, ct[top] = c;}void Add(int x, int y, int f, int c){add(x, y, f, c), add(y, x, 0, -c);}
};
class zkwMCMF : public Graph
{
public:int s, t;int fans, cans; // 最大流流量 和 最小费用int dep[V];bool vis[V];deque<int> q;bool spfa(){for (int i = 1; i <= n; i++)vis[i] = 0, dep[i] = INF;q.push_back(t), vis[t] = 1, dep[t] = 0;while (q.size()){int x = q.front();q.pop_front(), vis[x] = 0;for (auto i : g[x])if (fw[i ^ 1] && dep[to[i]] > dep[x] - ct[i]){dep[to[i]] = dep[x] - ct[i];if (!vis[to[i]]){vis[to[i]] = 1;if (q.size() && dep[to[i]] < dep[q.front()])q.push_front(to[i]);elseq.push_back(to[i]);}}}return dep[s] < INF;}int dfs(int x, int F){vis[x] = 1;if (x == t || !F)return F;int f, flow = 0;for (auto i : g[x])if (!vis[to[i]] && fw[i] && dep[x] - ct[i] == dep[to[i]] && (f = dfs(to[i], min(F, fw[i]))) > 0){cans += f * ct[i], fw[i] -= f, fw[i ^ 1] += f, flow += f, F -= f;if (!F)break;}return flow;}// 求最小费用最大流调用此函数即可// 求最大费用最大流，需要在建图时将费用取反，最后的最大费用为 -cansvoid mcmf(){while (spfa()){vis[t] = 1;while (vis[t]){for (int i = 1; i <= n; i++)vis[i] = 0;fans += dfs(s, INF);}}}
} network;

最后补一个蒋老师的最小费用可行流板子

struct MCFGraph
{struct Edge{int v, c, f;Edge(int v, int c, int f) : v(v), c(c), f(f) {}};const int n;vector<Edge> e;vector<vector<int>> g;vector<int> h, dis;vector<int> pre;bool dijkstra(int s, int t){dis.assign(n, numeric_limits<int>::max());pre.assign(n, -1);priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;dis[s] = 0;que.emplace(0, s);while (!que.empty()){int d = que.top().first;int u = que.top().second;que.pop();if (dis[u] < d)continue;for (int i : g[u]){int v = e[i].v;int c = e[i].c;int f = e[i].f;if (c > 0 && dis[v] > d + h[u] - h[v] + f){dis[v] = d + h[u] - h[v] + f;pre[v] = i;que.emplace(dis[v], v);}}}return dis[t] != numeric_limits<int>::max();}MCFGraph(int n) : n(n), g(n) {}void addEdge(int u, int v, int c, int f){if (f < 0){g[u].push_back(e.size());e.emplace_back(v, 0, f);g[v].push_back(e.size());e.emplace_back(u, c, -f);}else{g[u].push_back(e.size());e.emplace_back(v, c, f);g[v].push_back(e.size());e.emplace_back(u, 0, -f);}}pair<int, int> flow(int s, int t){int flow = 0;int cost = 0;h.assign(n, 0);while (dijkstra(s, t)){for (int i = 0; i < n; ++i)h[i] += dis[i];int aug = numeric_limits<int>::max();for (int i = t; i != s; i = e[pre[i] ^ 1].v)aug = min(aug, e[pre[i]].c);for (int i = t; i != s; i = e[pre[i] ^ 1].v){e[pre[i]].c -= aug;e[pre[i] ^ 1].c += aug;}flow += aug;cost += int(aug) * h[t];}return make_pair(flow, cost);}
};