重修 网络流建模
因为这一板块东西太多了所以拎出来单独讲
求最大权闭合子图
做法
定义： 点有点权 \(a_i\)，一个原有向图点集子集 \(G\) 的诱导子图，使得 \(\nexists (x\to y)\in E,x\in G,y\notin G\)，且 \(G\) 中点权和最大。
建网络流，具体如下：
-
原图上的有向边容量为 \(\inf\)。
-
对于 \(a_i\ge 0\)，从 \(S\) 向 \(i\) 连边，容量为 \(a_i\)。
-
对于 \(a_i<0\)，从 \(i\) 向 \(T\) 连边，容量为 \(|a_i|\)。
先统计出 \(All=\sum a_i[a_i\ge 0]\)，再求出最小割（最大流） \(Ans\)，答案为 \(All-Ans\)。
模板题：CF1473F Strange Set
Code
正确性证明
（一） 跑网络流最小割一定对应一个闭合子图。
显然，最小割一定是简单割，即割的每一条边要么有一端是 \(S\)，要么有一端是 \(T\)（因为中间每条边都是 \(\inf\)）。
设最小割为 \(\{S\to x\ |\ x\in A\}\cup\{x\to T\ |\ x\in B\}\)。
设 \(C=\{x\ |\ S\to x\}\)，则对应的闭合子图为 \((C-A)\cup B\) 的诱导子图。
通过简单的推导发现对应的闭合子图权值就是 \(All-Ans\)。
（二） 任何闭合子图都对应一个割。
设闭合子图点集中正权的 \(D\)，负权的 \(B\)，则对应的“割”为 \(\{S\to x\ |\ x\notin D\}\cup\{x\to T\ |\ x\in B\}\)，由上述推导发现 \(All-Ans\) 就是闭合子图的权值。
然后我们证明“割”为割，我们用反证法，假设还有流。由于 \(\{S\to x\ |\ x\notin D\}\) 都被割了，所以从 \(S\) 走一步只能到 \(D\) 中的点，而 \(D\cup B\) 为闭合子图，所以没有出路，矛盾，原命题成立。
（三） 由于最小割，所以闭合子图最大权，得证。
二分图最大匹配
从 \(S\) 到所有左部结点各连?条容量为 \(1\) 的弧，再从所有右部结点各连?条容量为 \(1\) 的弧到 \(T\)，最后把每条边变成?条由左部节点指向右部节点的有向弧，容量为 \(1\)。
最大流 \(=\) 最大匹配
由于每条边的流量均为 \(1\)，所以时间为 \(O(m\sqrt{n})\)，OI wiki证明。
上下界流
无源汇上下界可行流
也就是没有源汇，每个点的流量均平衡，每条边的流量在区间内，问是否可行。
若一条边 \(x\to y\) 的界为 \([A,B]\) 且 \(A<0\)，则拆成两条：
-
\(x\to y\) 界为 \([0,B]\)。
-
\(y\to x\) 界为 \([0,|A|]\)。
这样我们就保证了下界 \(\ge0\)。
先假设有解。我们让每一条 \(x\to y[A,B]\) 拆成 \(x\to y[A,A]\) 和 \(x\to y[0,B-A]\)。
所以，我们可以将 \(x\to y[A,A]\) 转化成 \(S\to x[0,A]\) 和 \(y\to T[0,A]\)。
这时候我们跑 \(S\to T\) 的最大流，如果与 \(S,T\) 相邻的边没有流满，说明无解，否则构造就是现在每条边的流量加上下界流就是答案。
有源汇上下界可行流
设这里原图的源汇为 \(S',T'\)，我们新建的为 \(S,T\)。
将原图的 \(T'\) 向 \(S'\) 连 \(\inf\) 的边，然后就是无源汇问题了。
有源汇上下界最大流
在求出有源汇上下界可行流后只用干两件事：
-
删掉 \(T'\to S'\) 的 \(\inf\) 边。
-
跑 \(S'\to T'\) 的最大流。
因为此时与 \(S,T\) 相邻的边都被「榨干」了，所以最大流不会搞到 \(S,T\) 相邻的边。
所以跑完最大流后 \(S\to T\) 还是满流的，所以可行。
有源汇上下界最小流
与上文不同的是，这次从 \(T'\to S'\) 跑最大流。
最小费用上下界可行流
其实和无源汇上下界可行流很像，就是多了费用。
-
建立附加源点 \(S\)，和附加汇点 \(T\)。
-
对于原图中每一个点（包括源汇）\(x\),令 \(d_x\) 代表 \(x\) 点的所有入边的流量下界减去出边的流量下界。
- 若 \(d_x>0\)，连 \(S\to x\)，容量为 \(d_x\)，费用为 \(0\)。
- 若 \(d_x<0\)，连 \(x\to T\)，容量为 \(|d_x|\)，费用为 \(0\)。
- 对于原图中每一条边 \(u\to v
[l,r]\) ，连边 \(u\to v\)，容量为 \(r-l\)，费用为 \(w\)。
最小费用有源汇上下界可行流
加边 \(T'\to S'\)，容量为 \(\inf\)，费用为 \(0\)。