网络流总结

基础知识

\qquad 流网络是一个有源点 $s$ 和汇点 $t$ 的有向图（不考虑反向边），记为 $G=(V,E)$。其中每一条边都有一个容量 $c(u,v)$ 和一个流量 $f(u,v)$。对于该网络中的一个流 $f$，如果其满足两个条件：1、容量限制，即每条边都满足 $0\le f(u,v)\le c(u,v)$；2、流量守恒，即除去源点汇点以外，每个点 $x$ 都满足 ${\sum }_{u\in V}f(u,x)={\sum }_{v\in V}f(x,v)$，那么我们称流 $f$ 是流网络 $G$ 的一个可行流。可行流的流量 $|f|={\sum }_{u\in V}f(s,u)-{\sum }_{v\in V}f(v,s)$，即从源点流出的流量减去流入源点的流量。

\qquad 残留网络是针对于原图中的一个流来说的。即，我们只能说“流 $f$ 的残留网络 $G_f$”。残留网络对于原图中的每一条边都增加一条反向边，这条反向边的流量与原图中边的流量相等。可以将残留网络中的边理解为“退流”。

\qquad 两个可行流是可以相加减的，叠加的方式就是每条边上的流量对应相加减，而且得到的结果也一定是原图的一个可行流。

\qquad 如果一个流网络中存在一条路径，这条路径中的任意一条边都没有达到满流（即 $f(u,v)<c(u,v)$），那么我们称这条路径为一条增广路径。

\qquad 流网络中的最大流指的是最大可行流，即第一要满足此流是一条可行流，其次要满足它的流量是本图所有可行流中最大的一个。

\qquad 流网络中的割指的是将图中的所有点分为 $S,T$ 两个点集，记作 $C(S,T)$。这两个点集要满足：1、$s\in S,t\in T$；2、$S\cap T=\varnothing$；3、$S\cup T=V$。割的容量定义为：${\sum }_{u\in S,v\in T}c(u,v)$，割的流量定义为：${\sum }_{u\in S,v\in T}f(u,v)-{\sum }_{u\in T,v\in S}f(u,v)$。流网络中的最小割指的是容量最小。

最大流最小割定理

\qquad 最大流最小割定理包含三条内容，这三条内容知一推二，分别是：1、可行流 $f$ 是最大流；2、可行流 $f$ 的残留网络中不存在增广路；3、存在某个割 $C(S,T)$，满足 $|f|=C(S,T)$。

最大流

\qquad 求最大流有两种算法：$EK$ 和 $dinic$。

EK

\qquad 根据最大流最小割定理，我们可以得知，当残留网络中不存在增广路时，该残留网络对应的流 $f$ 一定是最大流。$EK$ 算法便是基于这个原理，每次 $bfs$ 找残留网络中的增广路并将其增广，直到网络中不存在增广路为止。

\qquad $EK$ 算法时间复杂度为 $O(n{m}^2)$，不过网络流算法记时间复杂度用处不大。思路很简单，实现也很容易。

const int maxn = 110;
const int maxm = 5010;
typedef long long LL;
int n, m, S, T;
struct pic {int to, lst;LL cap;
}edge[maxm << 1];
int head[maxn], tot = -1/*边从0开始编号，目的是方便成对变换*/, pre[maxn]/*记录每个点第一次被搜到的前驱边是哪一条*/;
queue < int > q;
LL d[maxn];//记录到达当前点时当前增广路径的最大流量inline void add(int x, int y, int z) {edge[++ tot] = {y, head[x], 1LL * z};head[x] = tot;
}bool bfs() {//寻找增广路memset(vis, 0, sizeof vis);while(!q.empty()) q.pop();q.push(S), vis[S] = 1, d[S] = 1e9 + 7;while(!q.empty()) {int x = q.front(); q.pop();for(int i = head[x]; ~i; i = edge[i].lst) {int y = edge[i].to;if(!vis[y] && edge[i].cap/*有流量时才有意义去搜*/) {d[y] = min(d[x], edge[i].cap);//更新最大流量vis[y] = 1, pre[y] = i;if(y == T) return 1;//找到了一条增广路q.push(y);}}}return 0;
}LL EK() {LL ans = 0;while(bfs()) {ans += d[T];for(int x = T; x != S; x = edge[pre[x] ^ 1/*成对变换*/].to) edge[pre[x]].cap -= d[T], edge[pre[x] ^ 1].cap += d[T];//对增广路进行增广操作}return ans;
}
//main中
memset(head, -1, sizeof head);
scanf("%d%d%d%d", &n, &m, &S, &T);
for(int i = 1, x, y, z; i <= m; i ++) {scanf("%d%d%d", &x, &y, &z);add(x, y, z), add(y, x, 0)/*建残留网络，一开始流量都是0*/;
}
printf("%lld\n", EK());
}

dinic

\qquad 在 $EK$ 的基础之上，我们考虑优化。

\qquad $EK$ 每次 $bfs$ 只找出来了一条增广路进行增广，效率较低。$dinic$ 算法依据分层思想，每次找出多条增广路同时进行增广，而且还有三处小优化，总体时间复杂度 $O(n^{2}m)$，不过法律规定网络流不许卡 dinic。

bool bfs() {//找增广路memset(d, -1, sizeof d);//分层while(!q.empty()) q.pop();d[1] = 0/*源点层数为0*/, q.push(1), cur[1] = head[1];//当前弧优化while(!q.empty()) {int x = q.front(); q.pop();for(int i = head[x]; ~i; i = edge[i].lst) {int v = edge[i].to; LL w = edge[i].cap;if(d[v] == -1 && w) {d[v] = d[x] + 1/*记录点v在点x下一层*/, cur[v] = head[v];//记录从哪一条边开始跑if(v == n) return 1;q.push(v);}}}return 0;
}LL Find(int x, LL limit) {//limit:当前增广路径的最大流量if(x == n) return limit;//到了汇点LL flow = 0;//增广了多少流量for(int i = cur[x]; ~i && flow < limit/*优化1（最重要）：当flow>limit，再搜下去就无意义了，因为无法继续增广了*/; i = edge[i].lst) {cur[x] = i;//优化2：当前弧优化int v = edge[i].to; LL w = edge[i].cap;if(d[v] == d[x] + 1/*判断点v是否是点x的下一层*/ && w) {LL t = Find(v, min(w, limit - flow));if(!t) d[v] = -1;//优化3：如果这个点往后的流量是0，说明通过此点无法进行增广，直接删除即可edge[i].cap -= t, edge[i ^ 1].cap += t, flow += t;}}return flow;
}LL dinic() {LL flow = 0, ans = 0;while(bfs()) while(flow = Find(1, INF)) ans += flow;return ans;
}

模型

二分图匹配

\qquad 例题：飞行员配对方案问题，圆桌问题。

\qquad 套路：用最大流中边的容量来对边进行限制。

无源汇上下界可行流

\qquad 问题：给定一个包含 $n$ 个点 $m$ 条边的有向图，每条边都有一个流量下界和流量上界。求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。

\qquad 对于上下界的限制，形式化写出来是：$c_{low}(u,v)\le f(u,v)\le c_{up}(u,v)$，我们可以选择让不等式同时减去 $c_{low}(u,v)$ 从而变成只有上界的问题。但是减完之后可能会有点不满足流量守恒，此时我们需要建立超级源点、超级汇点，根据每个点是少流还是多流来对它们进行补偿或减少（即与源点连还是与汇点连）。而且为了保证这些点一定流量守恒，与源点、汇点相连的边必须要是满流的。所以我们连好与超级源点、汇点的边后，直接在新网络上跑最大流，如果跑出来的不是满流，那么原问题一定无解；否则，让新网络中每条边的流量加上原来的下界，就是原问题的一个可行流。

\qquad 核心 $Code$：

for(int i = 1, a, b, c, d; i <= m; i ++) {scanf("%d%d%d%d", &a, &b, &c, &d);add(a, b, d - c/*减去下节*/, c/*同时储存下界*/), add(b, a, 0, 0);A[a] -= c, A[b] += c;//记录每条边减去下界后，每个点流量的变化
}
int all = 0;
for(int i = 1; i <= n; i ++) {if(A[i] > 0) add(S, i, A[i], 0), add(i, S, 0, 0), all += A[i];//少流了，需要补else if(A[i] < 0) add(i, T, -A[i], 0), add(T, i, 0, 0);//多留了，需要放
}
if(dinic() < all) puts("NO");//不满流，无解
else {puts("YES");for(int i = 1; i <= (m << 1); i += 2) printf("%d\n", edge[i].cap + edge[i ^ 1].lower);//加上下界
}

有源汇上下界最大、最小流

\qquad 面对上下界，我们可以考虑建一条从汇点指向源点，容量为 $INF$ 的边，这样就转化为了无源汇上下界问题。我们可以先沿用无源汇上下界可行流的算法跑出一个可行流，然后将新添的边删去，再从源点向汇点跑出一个最大流，将这两个流相加便是答案。证明我也不太会……

\qquad 核心 $Code$：

for(int i = 1, a, b, c, d; i <= m; i ++) {scanf("%d%d%d%d", &a, &b, &c, &d);add(a, b, d - c), add(b, a, 0);A[a] -= c, A[b] += c;
}
int all = 0;
for(int i = 1; i <= n; i ++) {if(A[i] > 0) add(S, i, A[i]), add(i, S, 0), all += A[i];else if(A[i] < 0) add(i, T, -A[i]), add(T, i, 0);
}
add(t, s, INF), add(s, t, 0);//添加一条t->s，INF的边
if(dinic() < all) puts("No Solution");
else {int res = edge[tot].cap;//跑出来的可行流，注意不是dinic返回的流，因为dinic返回的是S到T的，我们需要的是s到t的edge[tot].cap = edge[tot ^ 1].cap = 0, S = s, T = t;printf("%d\n", res + dinic());
}

\qquad 对于最小流，我们让上述代码输出 $res-dinic()$ 即可。证明我还是不会……

多源汇最大流

\qquad 超级源点指向各个源点，各个汇点指向超级汇点，然后跑最大流即可。

最大流之关键边

\qquad 问题：如果升高一条边的容量可以使得最大流变大，那么我们称这条边为“关键边”。现在求网络中有几条“关键边”。

\qquad 我们思考，什么样的边可以成为关键边？

\qquad 在跑完最大流后，如果存在一条路径，这条路径中只有一条边是满流的，那么这条边一定是关键边。证明也很显然。那么，我们只需跑完最大流后，分别从源点和汇点开始 $dfs$，每次只走没满流的边。搜完之后，如果一条边的两端点分别被源点和汇点搜到，那么它一定是关键边。

最大流之拆点

\qquad 当我们有时要对点进行限制时，我们可以考虑拆点，在拆出的点之间加边来满足对点的限制。

\qquad 例题：[USACO07OPEN] Dining G，最长不下降子序列问题。

最大流建图实战

\qquad 例题：MPIGS - Sell Pigs，[SCOI2007] 蜥蜴，清理雪道。

最小割

\qquad 根据“最大流最小割定理”，我们可以得知，网络中最小割的容量就是最大流的流量，所以我们完全可以用求最大流的方法求最小割。

\qquad 但是，如果让求最小割的方案，怎么办呢？

\qquad 参考最大流求关键边的做法，我们可以从源点开始 $dfs$，每次只走没满流的边。最后如果有一条边的两个端点有一个被搜到了，另一个没有，那么这条边就要被割开。这也就意味着，整个图可以被分为“被搜到的点”和“没被搜到的点”两个点集。这样，其中一个合法方案就求出来了。

模型

最大权闭合子图

\qquad 对于图 $G=(V,E)$，如果它的一个子图 $G^{\prime }=(V^{\prime },E^{\prime })$ 满足 $V^{\prime }$ 中的任意一个点的任意一条出边都在 $E^{\prime }$ 内，那么就称 $G^{\prime }$ 是 $G$ 的一个闭合子图。如果给每个点附上点权（可为负），那么点权最大的一个闭合子图称为最大权闭合子图。

\qquad 如果给出一个带点权的图，我们怎么求解它的最大权闭合子图呢？

\qquad 首先，我们分别建立超级源点、超级汇点，超级源点指向所有正点权的点，边权为这个点的点权；所有负点权的点指向超级汇点，边权为这个点点权的绝对值；对于原图中的边，正常建在网络上，边权为 $INF$。此时，我们设所有正点权的点的点权和为 $r$。建好图之后，在图上跑一个最小割，设这个最小割的权值是 $s$，那么原图的最大权闭合子图的权值便是 $r-s$。

\qquad 例题：[NOI2006] 最大获利，太空飞行计划问题，[NOI2009] 植物大战僵尸。

最大密度子图

\qquad 我们定义一个图 $G=(V,E)$ 的密度为 $\frac{|E|}{|V|}$，最大密度子图指的便是图 $G$ 中使得 $\frac{|E^{\prime }|}{|V^{\prime }|}$ 最大的子图 $G^{\prime }=(V^{\prime },E^{\prime })$。

\qquad 既然是要让一个分式最大，那么就一定要用到 $0/1$ 分数规划。设当前二分的值为 $g$，那么我们就要尽可能找到 $|E^{\prime }|-g|V^{\prime }|$ 的最大值。在求最大值的过程中，我们可以借助最小割来推导式子并求解。

\qquad 核心 $Code$：

bool check(db x) {memset(head, -1, sizeof head), tot = -1;for(int i = 1; i <= m; i ++) add(E[i].first, E[i].second, 1), add(E[i].second, E[i].first, 1);for(int i = 1; i <= n; i ++) add(S, i, m), add(i, S, m), add(i, T, 1.0 * m + 2 * x - du[i]), add(T, i, 1.0 * m + 2 * x - du[i]);//m:赋的一个偏移量return 1.0 * m * n - dinic() > 0.0;
}

最小点权覆盖集

\qquad 问题：给定一张有向图，我们现在需要覆盖这张有向图中的所有边。对于一个点 $i$，我们可以花费 $W_i^{+}$ 的代价覆盖所有指向它的边，花费 $W_i^{-}$ 的代价覆盖所有它指出的边，问最小需要花费多少代价？

\qquad 对于这种有向图问题，我们可以考虑拆点套路，将一个点拆成 $i$ 和 $i+n$ 两个点。如果是无向图，那就直接连边即可。然后我们建立超级源点，从超级源点引一条容量为 $W_i^{+}$ 的边指向点 $i$；再建立超级汇点，从 $i+n$ 引一条容量为 $W_i^{-}$ 的边指向超级汇点。对于原图中的一条有向边 $(x,y)$，我们引一条从 $x$ 指向 $y+n$，容量为 $INF$ 的边。此时，我们跑出的最小割便是最小代价。

\qquad 跑完之后，我们遍历从源点指出的边。如果源点指向 $v$ 的边满流了，就说明我们要选择 $W_u^{+}$；最后，我们遍历一遍所有边，如果边 $(x,y)$ 此时没有选 $W_y^{+}$，那么我们就要选择 $W_x^{-}$。这样我们就得到了一组合法方案。

最大点权独立集

\qquad 问题：给定一张图，每个点有点权，我们需要选出一些点使得这些点在没有边相连的基础上点权和最大。

\qquad 根据经典结论：最大权独立=总-最小权覆盖，所以我们还按照上一种类型建边，跑出最小覆盖后用总点权减去最小覆盖即可。

最小割建图实战

\qquad 例题：CABLETV - Cable TV Network，骑士共存问题，文理分科。

费用流

\qquad 费用流全称为“最小费用最大流”或“最大费用最大流”，它是建立在最大流的基础之上的。费用流问题中，每条边不仅有容量，还有一个费用 $w$，表示每流过单位流量，就会产生 $w$ 的费用。费用流的算法基础是最大流的 $EK$，只不过把中间 $bfs$ 的过程改为了 $spfa$ 求最短路（即最小花费）。

EK

\qquad 大体跟最大流的 $EK$ 很像，只是改了 $bfs$ 为 $spfa$，还是很好理解的。

\qquad 核心 $Code:$

inline void add(int a, int b, int c, int d) {edge[++ tot] = {b, head[a], c, d}, head[a] = tot;edge[++ tot] = {a, head[b], 0, -d}, head[b] = tot;//注意，残留网络中边的费用是-d
}bool spfa() {memset(incf, 0, sizeof incf), memset(dis, 0x7f, sizeof dis);//incf:最大流量 dis:最小费用dis[S] = 0, incf[S] = INF, q.push(S), vis[S] = 1;while(!q.empty()) {int x = q.front(); q.pop(), vis[x] = 0;for(int i = head[x]; ~i; i = edge[i].lst) {int To = edge[i].to, Val = edge[i].val, Cost = edge[i].cost;if(Val && dis[To] > dis[x] + Cost) {dis[To] = dis[x] + Cost;incf[To] = min(incf[x], Val);pre[To] = i;if(!vis[To]) q.push(To), vis[To] = 1;}}}return incf[T] > 0;//判断能否跑到汇点
}void EK(int &flow, int &cost) {
[添加链接描述](https://www.luogu.com.cn/problem/P4015)	while(spfa()) {flow += incf[T], cost += incf[T] * dis[T];//flow:最大流 cost:最小费用for(int i = T; i != S; i = edge[pre[i] ^ 1].to) edge[pre[i]].val -= incf[T], edge[pre[i] ^ 1].val += incf[T];}return ;
}

模型

\qquad 费用流的题目较好写（？），主要有一类是费用流与上下界最大流的结合。

费用流与上下界最大流结合

\qquad 例题：[NOI2008]志愿者招募。

\qquad 带上下界，我们仍旧采取减去下界的方式转化。但是本题还有一个最主要的问题在于：一个志愿者工作的是一段区间，是“一对多”，这是正常建边无法做到的。遇到这种情况，我们可以考虑从区间终点向区间起点连一条边，转化为无源汇可行流来做即可。

费用流建图实战

\qquad 例题：餐巾计划问题，运输问题，负载平衡问题，分配问题，深海机器人问题，数字梯形问题，K取方格数。

最小割树

\qquad 最小割树上，任意两点路径上边权最小值为这两点的最小割权值。

\qquad 模板（核心 $Code$）：

void build(int l, int r) {if(l == r) return ;S = id[l], T = id[r];Add(id[l], id[r], dinic());int tmps1 = 0, tmps2 = 0;for(int i = l; i <= r; i ++) {if(d[id[i]] != -1) tmp1[++ tmps1] = id[i];else tmp2[++ tmps2] = id[i];}for(int i = l; i <= l + tmps1 - 1; i ++) id[i] = tmp1[i - l + 1];for(int i = l + tmps1; i <= r; i ++) id[i] = tmp2[i - (l + tmps1) + 1];build(l, l + tmps1 - 1), build(l + tmps1, r);
}

\qquad 例题：最小割树模板，[CQOI2016] 不同的最小割，[ZJOI2011]最小割，Pumping Stations。