网络流相关
网络流
内容主要为自己对网络流的一些理解和一些典例。
一些约定：
- s 为源点，t 为汇点
- 对于集合 \(S,T,T\subseteq S\)，约定 \(S-T\) 为从 \(S\) 中删掉 \(T\) 中每个元素之后的集合
- 网络流图为 \(G=(V,E)\)，边 \((u,v)\) 容量记为 \(c_{u,v}\)
最大流最小割定理和增广路定理
这两个定理是网络流问题的核心定理。
内容
最大流 = 最小割。
残量网络中不存在增广路是当前流为最大流的充要条件。
证明
若当前流为最大流，显然不存在增广路。
若当前流等于某个割，显然当前流为最大流，且该割为最小割。
若不存在增广路，我们证明当前流等于一个割。
令 \(S=\{v,\exist\ p_{s,v}\}\)，\(S\) 即 \(s\) 在残量网络中能到达的点的集合。令 \(T=V-S\)。显然 \((S,T)\) 是一个割，对于当前残量网络 \(G'=(V,E')\)，一定有 \(\forall x \in S,\forall y\in T\)，边 \((x,y)\) 满流，否则 \(y\in S\)。容易证明当前流恰好为 \(S\) 到 \(T\) 的所有边的容量和，也就是割的大小。因为此时原图 \(S\) 到 \(T\) 所有的边流量为容量，\(T\) 到 \(S\) 的边流量为 \(0\)，所以流量为 \(S\) 到 \(T\) 的边的流量之和，也就是割 \(S,T\)。
算法
Dinic
考虑对残量网络 bfs 分层，强制流量只能流向下一层，再进行一次 dfs，求限制下所有的增广路，搞定。
复杂度 \(O(n^2m)\)
每次增广复杂度为 \(O(nm)\)，共计增广 \(n\) 次，因为每次增广都会让 \(dep[t]\) 增加 1。
每次增广的复杂度不是很好证，但加了当前弧优化其实就很松。
代码记在脑子里了，不放了。
ISAP
咕咕咕
HLPP
咕咕咕
费用流相关
一般指最小费用最大流，暂时没啥感觉，不写。
最小割
非常常见的一个网络流模型应用。
核心思想
通过构造一个图的割到决策方案的映射，其中决策必须可拆分计算，求出最小的代价，一般来说决策的限制如果比较奇怪就应该考虑最小割。
常用于规划 \(0/1\) 独立贡献决策问题。
适用条件
- 不能存在负容量边权，我不知道有没有人会，反正我是不会。
1.最大闭合权子图问题
给定一张有向图，点带权（权可以为负），选一个子图出来，要求如果 \(u\) 选了那如果存在 \((u,v)\)，那 \(v\) 也要选。求最大权值和。
决策贡献独立，决策类型为 0/1。应该可以最小割。令割中与 \(s\) 同集合的点为选择的点，与 \(t\) 同一个集合的点为未选择的点。那么每个点应该和 \(t\) 连一条流量为权值的相反数的边，代表选它的代价，再对于每条 \((u,v)\) 从 \(u\) 向 \(v\) 连一条 inf 边,代表选了 \(u\) 不选 \(v\) 的代价。考虑这张图的一个最小割，它必然不会包含 inf 边，也就是说，我们选了 \(u\) 在 \(s\) 中一定会让 \(v\) 在 \(s\) 中，所以一定合法。然后发现原问题的每一个答案都可以和图上的一个不含 inf 边的割一一对应，故最小割就是原问题的答案的相反数。
这张图有负数，不行，所以考虑先默认选所有正数。那么选负数的代价为相反数，不选正数的代价为本身。
那么应该从 \(s\) 向正权点连边，从负权点向 \(t\) 连边，最后对于 \((u,v)\) 从 \(u\) 向 \(v\) 连 inf 边即可。