【学习记录】网络流

· · 个人记录

本文大部分内容借鉴自该专栏，也感谢曹神给推了这么牛的讲解。

以下所有最大流和费用流（最大/最小费用最大流）均可使用 Dinic 求解，我只会这个。

二者取一式问题

每个元素有两种选择 A,B，分别有 a_i,b_i 的收益。另有整体收益为某些元素均选 A 时收益 c，或某些元素均选 B 时收益 d。建模方式为连边 (S,i,a_i) 和 (i,T,b_i)，定义割中保留的边表示选。整体收益建一个新点 t，选 A 则连边 (S,t,c) 和 (t,x,\infin)，选 B 则连边 (t,T,d) 和 (x,t,\infin)。该图的边权和减去最小割即为答案，容易发现这是对的，因为 \infin 边不会被割，若某限制中有选错的，则收益边必须被割。最小割可用最大流求解，板题提交记录。

P2057 善意的投票

本题中要求最小化代价，考虑直接将代价作为流量，并定义割掉表示选，这样直接求最小割得到最小代价。考虑如何刻画 (x,y) 选择不同时 1 的代价，直接连 (x,y,1),(y,x,1) 两条边即可，画图可以发现若两点割掉的边不同，则必定割两条新边中的一条。因此这样是对的，直接求最小割即为答案，提交记录。

本题也可以转化成收益做，即转化为求最大的不冲突数。那么每对朋友需要新建两个点表示收益，求出最大值后用 n+m 减去即为答案，提交记录，由于点数较多，比上一种略慢一些。

WyOJ342 捆绑销售

求分数最大值考虑二分，则要求 \frac{(\sum a_i)^2}{\sum a_i^2}\ge k，移项拆式子可得 \sum_{i<j} 2a_ia_j+\sum_i(1-k)a_i^2\ge0，因此求左式最大值即可。显然可以建模到网络流图上，前式是整体收益，后式必为负，因此提前求和计入答案，并转化成不选的正收益。问题在于题目中还有捆绑限制，即选 x 后必选 y，因此需求最大权闭合子图，方式为直接连边 (x,y,\infin)，该边无法被割，因此不能选 x 却不选 y，可以求出正确答案。网络流需要浮点数流量，有一些细节，提交记录。

无源汇上下界可行流

考虑先将所有边的流量设为下界，则每条边剩余流量为上下界之差，以此可建出差网络。然而此时不一定满足流量守恒，需要用差网络上的流量使其守恒。

具体地，设 w_u 表示流量均为下界时 u 点的净流入量，若为负则表示有 -w_u 的净流出量。以 w_u>0 为例，此时差网络上需要 u 的净流出量为 w_u，以使得总流量守恒。因此建立源点 S'，并由源点向 u 连流量为 w_u 的边，则差网络上该边流满且 u 点流量守恒时，原网络上流量也守恒；同理，若 w_u<0，则由 u 向汇点 T' 连流量为 -w_u 的边即可。此处本质上是将流量下界所带来的净流量用新源汇等效替代了。

此时以 S',T' 为源汇跑最大流，若所有代表净流量的边均满流，则目前流量与流量下界之和即为一组可行流；否则原网络无可行流。具体判断时由于源点流出量与汇点流入量相等，只需判断源点出边是否均满流即可。代码。

有源汇上下界可行流

只需加入一条由 T 到 S，流量为 \infin 的边，即可转化为等价的无源汇网络，可以直接做。

有源汇上下界最大流

先求出一组可行流，此时新边 (T,S) 的流量即为目前流量。考虑去掉该边和 S',T'，重新以 S,T 为源汇在残量网络上跑最大流，答案即为两个流量的和。实现上由于有解时 S',T' 所连边均已流满，无需处理；同时可行流 f 产生了一条 (S,T,f) 的反悔边，而 (T,S) 不会被访问，因此不进行任何处理时，残量网络上 S,T 为源汇的最大流即为答案。代码。

有源汇上下界最小流

与最大流类似，只是求出可行流后要以 T,S 分别为源汇跑最大流，并从可行流中减去得到答案，可理解为把可退流均退掉了。此处没有简便实现，需要清掉边 (T,S) 并累加答案。代码。

P5192 Shoot the Bullet

以每天为左部点，每位少女为右部点，由源点 S 向左部点连 [0,D_i] 的边，由右部点向汇点 T 连 [G_x,\infin] 的边，左部点和右部点间连 [L,R] 的边，求有源汇上下界最大流即为答案。提交记录。

无源汇上下界费用流

所求为费用达到最值的可行流，做法也与可行流类似，所建新边费用均为 0，直接跑出差网络的费用流即为答案。

P4043 支线剧情

据题意建边，设流量为途径次数，所求即为最小费用。由于每条边均需被覆盖至少一次，这些边流量限制为 [1,\infin]，费用为 t；同时任意点都可直接回到 1 号点，因此每个点都向 1 号点连 [0,\infin]，费用为 0 的边。该网络的无源汇上下界最小费用流即为答案。提交记录。

有源汇上下界费用流

同可行流一样，只需加入一条由 T 到 S，流量为 \infin，费用为 0 的边，即可转化为等价的无源汇网络。注意此时直接求出的是可行流的费用最值，而对流量没有保证。若还要求流量最大/最小，还需要像不带费用时一样在残量网络上跑费用流并累加才行。

P7173 有负圈的费用流

考虑清除所有 c<0 的负边 (u,v,f,c)，方式为将其强制流满，即令其流量限制为 [f,f]，并加入反边 (v,u,f,-c) 用于反悔。非负边流量限制为 [0,f]，费用不变。对该网络求有源汇上下界最小费用流，可得到费用最小的可行流。为了达到流量最大，还需在残量网络上以 S,T 为源汇跑费用流，并将所得流量和费用累计入答案。当然这里与有源汇上下界最大流一样，最大流量也可以不处理直接得到。提交记录。

最小费用流的对偶

最小费用流可表示为 \min\sum g_{u,v}c_{u,v}，限制为 g_{u,v}\le f_{u,v}，且 \forall x,\sum g_{u,x}-\sum g_{x,v}=b_x。其中 f,c 分别为流量限制和费用，g 为实际流量，b 为某点要求的净流入量，为负则绝对值为净流出量。

分别以 d_{u,v},p_u 为对偶变量时，对偶得到 \max \sum-d_{u,v}f_{u,v}-\sum b_up_u，限制为 -d_{u,v}+p_v-p_u\le c_{u,v},d_{u,v}\ge 0。由于 f 为整数，d 越小越好，因此 d_{u,v} 会取 \max(0,p_v-p_u-c_{u,v})。据此整理所求式可得 -(\min(\sum\max(0,p_v-p_u-c_{u,v})f_{u,v}+\sum b_up_u))。因此若得到如此形式的式子，可转化成费用流求解。

P3337 防守战线

设 p_i 为所修塔数的前缀和，即前 i 个位置上修塔总数。转化可得所求为 \min\sum(c_i-c_{i+1})s_i，限制为 p_i-p_{i+1}\le 0,p_{l-1}-p_r+d\le0。考虑将 x 不大于 0 的限制转化为 \infin\times \max(0,x) 放入 \min 式中，即可得到上述形式的式子。

根据变量含义建出网络流图，以下 (f,c) 表示流量上限为 f，费用为 c。需要由 i+1 向 i 连 (\infin,0) 的边，由 r 向 l-1 连 (\infin,-d) 的边。另有 b_i=c_{i}-c_{i+1}，该净流量要从源汇处取得，即若 b_i>0，由 S 向 i 连 (b_i,0) 的边；否则由 i 向 T 连 (-b_i,0) 的边。根据上述对偶，该网络最小费用最大流的费用即为答案的相反数。

注意到该网络中费用非正，存在负圈，因此需使用有负圈的费用流求解，这也是我去学上述内容的出发点。本题数据范围较大，费用流只能通过 70 分，提交记录。另外注意到转化后的网络中不存在负边，可以用 Dijkstra 代替 SPFA，然而过得更少了。想通过本题可能需要使用原始对偶或单纯形，然而这不是本文所讨论的内容，同时我不会也不想学，不再叙述。