网络流进阶

· · 算法·理论

上下界网络流

网络流中 N,M 一定要尽量开大，为后续加边做准备。

无源汇可行流

先将下界流满，只考虑上界限制（此时新上界减去下界），但这会导致点上流量的不平衡。有的点流入流量比流出多，会积攒一些流量，需要多流出；有的流出更多，需要多流入。

强制这些限制，最大流表示可行方案。

是否存在可行流对应这样的最大流是否可以满流。构造则看最大流中每条边流量加下界。

有源汇最大流

转化成无源汇，方法是从 t 向 s 连流量要求在 [0,\infty] 内的边。

对这个图先跑一遍无源汇可行流，得到一种可行流对应的残量网络，可行流不保证 s 到 t 的流量，在这个网络上继续增广跑最大流，加上可行流流量即为答案，原因是增广的过程不会破坏原先点上的平衡。

有源汇最小流

同样在可行流残量网络上调整。增广和退流是两个对应的操作，均不会对点上的流量产生影响，这里考虑退流，将 s 到 t 路径上流量转移到其他地方，即求残量网络上 t 到 s 的最大流，用可行流流量减去这个值即可（实现中最大和最小流要删除 t\to s，容量为 \infty 的边）。

网络流应用

二分图最大匹配

限制为：左右两边每个点都至多与异侧连一条边，转化为网络流流量限制。

#### 二分图最大权匹配 在上面基础上对左右间连边赋费用即可，最大权所以取负，若非完美匹配则补点。 （Konig 定理：二分图最大匹配=最小点覆盖） ## 最小割应用 > 最小割除了数值上等于最大流，本质上与网络流无任何关系。 #### 二元关系：P1361 $n$ 个物品，选 $i$ 收益 $v_i$，不选收益 $w_i$，若干组合 $(i,j)$，同时选收益 $c_{i,j}$，同时不选收益 $t_{i,j}$，求最大收益，数量级 $10^3$。 #### Sol > - 题目类型：若干个物品每个选或不选，分出若干二元组，组内每种取法有对应收益或花费，求最大收益。 > > - 想法： > - 构造有源汇的带权有向图，图中 $S$ 可以到达的部分选，其余部分不选。 > - 答案初始为所有能得到的收益之和（包括冲突），接着在图上不断删边，表示改变点是否被选择的状态，边权上体现这样的花费（或得不到的收益），删边最终的要求是选择方案合法，即 $S$ 不能到达 $T$。 > - 同时要求删去的部分价值最少，这便是求这个图的最小割，答案即为收益和减去最小割。 > - 构造这个图，以两个物品情况分析。 > - $S\stackrel a\longrightarrow i/ i\stackrel b\longrightarrow T/S\stackrel c\longrightarrow j/ j\stackrel d \longrightarrow T/i\stackrel e\longrightarrow j/j\stackrel f\longrightarrow i$ ，$ij$ 中选一个也有对应方案时连 $ef$，对所有选取情况列出 `边之和=花费和` 方程，解方程时利用 $S\to u/u\to T$ 边权仅与 $u$ 有关，$u\to v/v\to u$ 边权必与两点都有关（*），可以解出边权。 > - 若上述方案不能得出符合（*）解，尝试每个边权恰为某个收益或花费情况，`abcd` 对应的四条边是必须的，分析想要选哪些点时，这些边中哪些要删去，会使哪些收益或花费为权值的边被强制删掉。 > - 这里强制删掉指若不删掉则 $S$ 可以通过这条边到达计划删除的点，即需要有这么一条路径。 > - 而且注意新加的部分对 $i,j$ 是对称的，此时花费常会体现在 $S/T$ 连向新点的边上，新点向 $i,j$ 连边可以为 $\infty$，不可删除。 本题中，第一种构造图方案行不通，分析： - 收益和：$\sum v+\sum w+\sum c+\sum t$。 - 选 $i,j$，删 $bd$，需要删 $v$，则有路径 $S\to v\to i,j$（指路径上有这个边权）。 - 都不选，删 $ac$，需要删 $w$，则 $i,j\to w\to T$。 - 选 $i$，删 $bc$，$v$ 和 $w$ 都要删，$S\to v(w)\to j/i\to w(v)\to T$。 - 选 $j$，删 $ad$，都删，$S\to v(w)\to i/j\to w(v)\to T$。 构造：$S \stackrel {v_{i,j}} \longrightarrow x\stackrel {\infty} \longrightarrow ij/ij\stackrel {\infty} \longrightarrow y\stackrel {w_{i,j}} \longrightarrow T$，$a=v_i$，$b=w_i$，$c=v_j$，$d=w_j$，收益和减最小割即可。 #### 限制关系：CF808F $n$ 个物品，每个物品有属性 $l_i,c_i,p_i$，要求从中取若干物品，满足 $\sum p\ge k$ 且 $\forall c_i+c_j$ 非质数，求 $\max\{l_i\}$ 最小值。 $n,l_i\le 100$，$1\le c_i,p_i\le 10^5$。 #### Sol 限制过多，简化之，从 $l$ 开始：二分 $maxl$，后续只考虑 $l_i\le maxl$，计算满足 $c$ 条件下 $\sum p$ 最大值。 选取类问题，想强制选/不选的关系建图是否是 $k$ 部图。如本题中以物品为点，$c_i+c_j$ 为质数则连边 $(i,j)$，若按 $c_i$ 奇偶性分为两组，除了 $c_i=c_j=1$ 的情况不会有同组连边，这种情况可以只留下 $p$ 更大的物品，二分图关系成立。 考虑最小割，将损失体现在边权上，这里即为未选取点的 $p$。用每条 $S$ 到 $T$ 的路径表示一组限制，想使选取合法则每条路径上至少删掉一条边，符合最小割模型，这样的好处是，每条路径形式相同。则 $S$ 向 $c_i$ 为奇点连边，边权为 $p_i$，$c_i$ 为偶点则向 $T$ 连边。 $\sum p$ 最大值则为所有 $p$ 之和减去上图最小割，一次二分完成。 ## 全局最小割：SW算法 无向正权图，求一组 $(s,t)$ 使得此图 $s-t$ 最小割最小，要求 $O(n^3)$。 #### Sol 只讲过程，不谈证明。 > 结论： > > - $G(V,E)$，点集 $A$ 初始为空，定义点集外点 $X$ 到 $A$ 的距离 $dis(X,A)=\sum _{v\in A} d(X,v)$，其中 $d(X,v)$ 为两点**边权**（不连边则为 $0$）。 > - 对 $V$ 中所有点，每次加入 $dis(X,A)$ 最大的点 $X$（$dis$ 随 $A$ 动态变化），则以当前最后加入两个点为源汇的，在以 $A$ 为点集的诱导子图中的最小割，即为最后一个点加入时的 $dis$。 1. 每次对当前图做上述过程，用最后加入的两个点在当前整张图的最小割更新答案。 2. 将这两个点 $s$ 和 $t$ 合并，具体地，删除其中一个点 $s$，并对所有还存在的点 $u$，更新 $w(t,u)\stackrel +\longleftarrow w(s,u)$，其中 $w$ 为两点间双向边权。 3. 重复第一步，直到所有点被合并到一个点，这整个过程是 $O(n^2\log n+nm)$ 的，实现中注意重边边权叠加。