本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-05-20 21:04:59

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

以下所有最大流和费用流（最大/最小费用最大流）均可使用 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，然而过得更少了。想通过本题可能需要使用原始对偶或单纯形，然而这不是本文所讨论的内容，同时我不会也不想学，不再叙述。