网络流的求法
https://www.cnblogs.com/caijianhong/p/16863491.html
misc
复杂度分析
-
Dinic 的复杂度上界为 \(O(n^2m)\)。
- 但是特殊情况下会更快，如二分图匹配是 \(O(m\sqrt n)\) 的；确定流量上限 \(f\) 时，复杂度为 \(O(mf)\)。
-
最小费用最大流的复杂度上界为 \(O(nmf)\)。
-
注意，单路增广和多路增广没有复杂度区别，后者只是常数优化。
-
无论哪一种写法，当前弧优化都是必要的，否则复杂度错误。
misc
- 多源汇：建立超级源点和汇点。
- 点 \(u\) 自带流量 \(w\)：连边 \((S,u)=w\)。
- 点 \(u\) 最终需要接受流量 \(w\)：连边 \((u,T)=w\)。
- 经过点 \(u\) 有容量限制 \(w\)：将这个点拆成 \(u,u'\)，一个入点（连边 \((v,u)\)），一个出点（连边 \((u',v)\)），中间连 \((u,u')=w\)。
- 无向图：连两条有向边（现在你有了四条边）
无源汇上下界可行流
这个图是无源汇的，那么可行流在这里指：每个点都流量平衡。
对于所有边 \(u\to v\) 带有 \([l,r]\) 的流量限制，使得 \(u\) 点强制流出 \(l\)，\(v\) 点强制流入 \(l\)，记录每个点的流入和流出，流入减流出记为 \(d_u\)。这个时候是不满足流量平衡的，拿出超级源汇 \(S,T\)，枚举点 \(u\)，如果 \(d_u>0\) 就是流入更多，那么使它流出，\(u\to T\) 需要流 \(d_u\)；反之流出更多，使它平衡，\(S\to u\) 需要流 \(-d_u\)。
将每条边的流量限制改为 \(r-l\)，对所有边添加反向边，以 \(S\) 为源点，\(T\) 为汇点，跑最大流。如果 \(S\) 连出的点没有满流（由于 \(S,T\) 流量相等，\(T\) 流入的边也没有满流），则没有可行流；否则这就是。
有源汇上下界可行流
- 设原图的源汇为 \(s,t\)。\(t\to s\) 连接容量 \(\infty\) 的边。
- 进行无源汇上下界可行流。
有源汇上下界最大/小流
- 跑一遍有源汇上下界可行流，如果没有就真的没有了。
- 删除 \(t\to s\) 的巨大无比的边。
- 删除 \(S,T\) 连出的流量平衡边。
- 对于最大流，以 \(s\) 为源点，\(t\) 为汇点，在当前残量网络上跑最大流。
- 对于最小流，以 \(t\) 为源点，\(s\) 为汇点，在当前残量网络上跑最大流。
最小割及应用
在网络图 \(G=(V,E)\) 中，割被定义为一种点集的划分方式：将所有的点划分成两个集合 \(s,t\)，满足 \(s\cup t=V,s\cap t=\varnothing,S\in s,t\in T\)。这个割的权值被定义为 \(\forall(u,v)\in E,u\in s,v\in t\) 的 \(w(u,v)\) 之和。
最大流-最小割定理：在任意网络中，最大流等于最小割。
证明
我们记最大流是 \(\max flow\)，最小割为 \(\min cut\)。根据常识：
\[\max flow=\min cut\Leftrightarrow \begin{cases} \max flow\leq \min cut\text{ (I)}\\ \max flow\geq \min cut\text{ (II)}\\ \end{cases}\]对于 \(\text{(I)}\) 式：对于任意一个割 \(cut\)，最大流不会超过这个割的权值（权值是容量，不能比容量还大），所以 \(\max flow\leq cut\Rightarrow\max flow\leq \min cut\)。
对于 \(\text{(II)}\) 式，对于一个最大流 \(flow\)，在残量网络上 \(S,T\) 必然不连通（否则 \(flow\) 不是最大流），我们把导致不连通的边（满流的边）拿出来做一个割，则割的权值不超过最大流，即 \(\max flow\geq cut\Rightarrow\max flow\geq \min cut\)。
所以 \(\max flow=\min cut\)，证毕。
方案
用你喜欢的最大流算法跑出一个最大流，沿着残量网络从 \(S\) 找到的点就属于点集 \(s\)。
注意，最大流和最小割只有数值相等的关系（正如 SAM 和后缀树只有形态相似的关系），建最小割的图时不能按照网络流思想建。
最大权闭合子图
我们说一个有向图是一张图的闭合子图，那么：
- 它是一个有向图的子图；
- 如果一个点在闭合子图中，它在原图中的所有出边指向的点都在这张新的闭合子图中。
那么最大权闭合子图就是权值和最大的子图。
建图方法：正权点连 S，负权点连 T，其他边保留为无穷大，答案是正权点之和 - 最小割。
例题：连通块
\(k\) 棵树，点带权 \(a_i\) 可负，求一个权值集合，使得它在 \(k\) 棵树上都是连通块。\(n\leq 50000\)
考虑如果固定根，把 \(k\) 棵树拉出来，则这时，若选择了一个权值，则它在所有树上的父亲都要选。
将权值建点，连向它在每棵树上的父亲。跑最大权闭合子图（S 连向正数，负数连向 T，最小割）。
点分治。
奖励模型
\(n\) 个物品，买下第 \(i\) 个物品需要 \(cost_i\)，不买这一个物品需要花费 \(pay_i\)，如果同时买了 \(u,v\) 则奖励 \(money_{u,v}\)，如果同时不买 \(u,v\) 也奖励 \(orz_{u,v}\)，求最大获利。
令 \(m=\sum_i cost_i+\sum_{u,v} money_{u,v}+\sum_{u,v} orz_{u,v}\)。我们最终答案 = m - 最小割。
每个物品建一个点。注意我们割掉哪条边就代表我们不选这个决策。假如我们说 S 连向这个点是 \(pay_i\)，这个点连向 T 是 \(cost_i\)，就是说我们割掉左边就是买，割掉右边就是不买。
然后建奖励点：
- 同时买 \(u,v\)：建点 \(P\)，\(u,v\to P\to T\)，其中 \(P\to T\) 的权值是 \(money_{u,v}\)，另外两条边是 \(\infty\)。
- 同时不买 \(u,v\)：建点 \(P\)，\(S\to P\to u,v\)，其中 \(S\to P\) 的权值是 \(orz_{u,v}\)，另外两条边是 \(\infty\)。
只有某一侧的边全部割掉，它们对应的另一侧的奖励点才能保留，才不会被减掉。
不等式组
\(n\) 个变量 \(m\) 种取值。\(q\) 个形如【不可以同时满足 \(x_i\geq a\) 且 \(x_j\leq b\)】的条件。求一组解，或者求权值和最小的解。
对于一个变量的所有取值开一条链，这些限制相当于一条链到另一条链的边，然后最小割。参考 [HNOI2013]切糕。
平面图最小割
边与边只在顶点相交的图被称为平面图。
对于一个平面图，都有其对应的对偶图：
- 平面图被划分出的每一个区域当作对偶图的一个点；
- 平面图中的每一条边两边的区域对应的点用边相连，特别地，若两边为同一区域则加一条回边（自环）。
这样构成的图即为原平面图的对偶图。
平面图最小割等于对偶图最短路。
二分图相关
定义
- 图的最大团：是图的一个最大的点集 \(V\)，满足 \(\forall i,j\in V\)，\(i,j\) 之间有边。
- 图的最大独立集：是图的一个最大的点集 \(V\)，满足 \(\forall i,j\in V\)，\(i,j\) 之间没有边。
- 图的最小点覆盖：是图的一个最小的点集 \(V\)，满足对于每一条边，它的两端至少有一端在 \(V\) 中。
- 图的最大匹配：是图的一个最大的边集 \(E\)，满足对于每一个点，这个点至多有一条边集中的边与它相连。
- 图的最小边覆盖：是图的一个最小的边集 \(E\)，满足对于每一个点，至少有一条边 \(e\in E\) 使得这个点是 \(e\) 的一端。
- DAG 的最小路径覆盖：是 DAG 的一个点不相交路径集合，每个点都在恰好一条路径上。
- DAG 的最小链覆盖：是 DAG 的一个链组成的集合，每个点都在至少一条链上。
- DAG 的最长反链：是 DAG 的一个点集，满足点集中任意两点不可达。
定理
-
一般图：最大团 = 补图最大独立集。
-
一般图：最大独立集 + 最小点覆盖 = n。
-
Hall 定理（二分图）：二分图存在完美匹配，当且仅当，对于所有左部点 \(S\) 都有 \(|nxt(S)|\geq |S|\)，其中 \(nxt(u)\) 是 \(u\) 的出边指向的右部点集合，\(nxt(S)=\bigcup_{u\in S}nxt(u)\)。
-
二分图：最小点覆盖 = 最大匹配。最小点覆盖的方案是，（证明）
- 从左部每个非匹配点出发，再执行一次 dfs 寻找增广路的过程（一定会失败），标记访问过的节点。
- 取左部未被标记的点、右部被标记的点，就得到了二分图最小点覆盖。
-
二分图：最大独立集 = n - 最大匹配。
- 最大独立集的方案是最小点覆盖的反面。就是说这两个点集加起来为全集。
-
二分图：最小边覆盖 = 最大匹配。
- 最小边覆盖的方案是，选出最大匹配中的边，剩下失配点找一条另一端是匹配点的边。
-
DAG：最小路径覆盖的做法，是
- 将每个点拆成入点和出点，\(\forall u\in V,inn_u\to out_u\)，\(\forall (u,v)\in E,out_u\to inn_v\)。
- 然后跑二分图最大匹配。
- 方案就是最大匹配了。
-
DAG：最小链覆盖的做法是
- 对 DAG 求传递闭包。
- 对传递闭包求最小路径覆盖。
-
Dilworth 定理（DAG）：最长反链 = 最小链覆盖。
欧拉回路
直接 dfs，然后要求每条边只能被遍历到一次，比如 dfs(u) 找到了出边 \((u,v)\) 则 dfs(v) 完之后加上 \(v\to u\) 这条边。