- 关键点
- 特殊图
(u,v,c,w) 表示 u→v，容量 c，费用 w。
一般用最大 / 小费用可行流模型。
注意基本事实：EK 不会出现负环，因而不会退掉 S,T 的邻边。
关键点
「AGC018C」Coins
注意到一共恰有 X+Y+Z 个人，令 N=X+Y+Z，因而可以首先假定每个人都选择金币，再用费用流调整。
对每个人建点 P1,…,PN，对每一组建点 F1,F2。
对于 i=1,…,N，连边 (Pi,F1,1,Bi),(Pi,F2,1,Ci)。
对于 i=1,…,N，连边 (S,Pi,1,−Ai)。
连边 (F1,T,Y,∞),(F2,T,Z,∞)。
以 S,F1,2,T 为关键点，讨论两两之间（不经过其他关键点）的最短路：
S→F1：将一个选择金币的人 i 改为选择银币，费用为 Bi−Ai。
S→F2：将一个选择金币的人 i 改为选择铜币，费用为 Ci−Ai。
F1→F2：将一个选择银币的人 i 改为选择铜币，费用为 Ci−Bi。
F2→F1：将一个选择铜币的人 i 改为选择银币，费用为 Bi−Ci。
从而一条增广路也有四种形态。用堆维护即可。
「AGC034D」Manhattan Max Matching
注意到最大 Manhattan 距离可以直接拆符号，从 4 种可能的符号中取 max。
对每个红点建点 R1,…,RN，对每个蓝点建点 B1,…,BN，对每一种符号建点 F1,F2,F3,F4。
对于 i=1,…,N，连边 (S,Ri,RCi,∞),(Bi,T,BCi,∞)。
对于 i=1,…,N，连边 (Ri,F1,∞,RXi+RYi),(F1,Bi,∞,−BXi−BYi)。
对于 i=1,…,N，连边 (Ri,F2,∞,RXi−RYi),(F2,Bi,∞,−BXi+BYi)。
对于 i=1,…,N，连边 (Ri,F3,∞,−RXi+RYi),(F3,Bi,∞,BXi−BYi)。
对于 i=1,…,N，连边 (Ri,F4,∞,−RXi−RYi),(F4,Bi,∞,BXi+BYi)。
以 S,F1,2,3,4,T 为关键点，讨论两两之间（不经过其他关键点）的最短路：
S→Fj：为一个未匹配的红点选择第 j 种符号。
Fj→T：为一个未匹配的蓝点选择第 j 种符号。
Fj→Fk：将一个选择第 j 种符号的红点改成选择第 k 种符号，或将一个选择第 k 种符号的蓝点改成选择第 j 种符号。
「2019 ICPC Asia Shanghai Regional」Blood Pressure Game
bj 匹配 (i,i+1) 的费用是 |ai−bj|+|ai+1−bj|−|ai−ai+1|，最后那一项是已经确定的，前两项可以类似上一题直接拆符号，因此和上一题一样做即可。
「NOI2019」序列
解法 1
考虑到容量是个 ≤ 的限制，因此我们不妨改写成只能选择最多 k−L 种不同下标的匹配。
对每个位置建点 Ai,Bi，建中转点 U,V,T′。
对 i=1,…,n，连边 (S,Ai,1,ai),(Bi,T′,1,bi)。
对 i=1,…,n，连边 (Ai,Bi,1,0)。
对 i=1,…,n，连边 (Ai,U,1,0),(V,Bi,1,0)。
连边 (U,V,k−L,0),(T′,T,k,∞)。
以 S,U,V,T 作为关键点，讨论两两之间（不经过其他关键点）的最短路：
S→T：匹配一组两边都未匹配的 (ai,bi)，费用为 ai+bi。
S→U：选择一个未匹配的 ai，费用为 ai。
V→T：选择一个未匹配的 bi，费用为 bi。
S→V：选择一组 (ai,bi)，其中 ai 未匹配，bi 已经过 V 匹配，费用为 ai。
U→T：选择一组 (ai,bi)，其中 bi 未匹配，ai 已经过 U 匹配，费用为 bi。
U→V：直接经过这条边匹配，费用为 0；或是将经过 U,V 匹配的一组 (ai,bj) 换成直接匹配，要求 i=j，事实上不存在这种情况。
V→U：反悔一组经过这条边的匹配，费用为 0；或是将一组 (ai,bi) 改为经过 U,V 匹配，事实上也不存在这种情况。
解法 2
考虑不观察直接硬做，将匹配的位置划分为三种：出现在 {ci} 中，出现在 {di} 中，同时出现在两侧。
对每个下标建点 P1,…,Pn，对每一种下标建点 F1,F2,F3。
枚举第三种的数量为 p，建图：
对于 i=1,…,n，连边 (Pi,F1,1,ai),(Pi,F2,1,bi),(Pi,F3,1,ai+bi)。
对于 i=1,…,n，连边 (S,Pi,1,0)。
连边 (F1,T,k−p,∞),(F2,T,k−p,∞),(F3,T,p,∞)。
最短路类似 Coins 一题，不再讨论。我们在增加 p 的时候会导致两条满流边容量减 1，一条满流边容量加 1。
不妨假设初始时存在 (T,S,∞,0)，转化为无源汇问题。那么给 (u,v) 容量加 1 相当于从 v 到 u 增广 1 单位流量，给 (u,v) 容量减 1 相当于从 u 到 v 增广 1 单位流量（均不经过 (u,v)）。
注意到由于图形态特殊，此处任意增广路一定经过 S,T。而可以注意到若环包含 S,T 之间的路径则必然不优，因此只需要考虑在 S,u 之间寻找增广路。
「2022 ICPC Asia Hangzhou Regional」RPG Pro League
解法 1
显然可以把职业组成理解成选取一组 D, S, B 然后再选择一个 D 或 S。因此我们对每个人建点 P1,…,Pn，对每一队的四个角色建点 F1,F2,F3,F4。
由于队伍数不确定，考虑枚举队伍数 k，建图：
对于 i=1,…,n，连边 (S,Pi,1,pi)。
对于 i=1,…,n 且 `D'∈Si，连边 (Pi,F1,1,0)。
对于 i=1,…,n 且 `S'∈Si，连边 (Pi,F2,1,0)。
对于 i=1,…,n 且 `B'∈Si，连边 (Pi,F3,1,0)。
对于 i=1,…,n 且 `D'∈Si∨`S'∈Si，连边 (Pi,F4,1,0)。
连边 (F1,T,k,−∞),(F2,T,k,−∞),(F3,T,k,−∞),(F4,T,k,−∞)。
关键点显然是 S,F1,2,3,4,T，最短路部分类似前文，不再赘述。
k 增加时，由上一题的分析，只需要尝试从 S 到 Fj 增广。
修改时也要考虑退流。由于 T 的邻边均满流，只需要考虑消去不经过 T 的负环，即寻找一个 Fj 消去 S→Fj→S 的环。
解法 2
考虑先求出 k。可以将 pi 置零后做模拟，也可以二分并使用 Hall 定理判定。
现在我们假设不存在任何 (S,Pi) 边，然后按照 pi 从小到大加入边。注意到不可能出现不经过 T 的负环，因此只需要考虑 S 到 T 的增广路。
修改的做法和解法 1 一致。
解法 3
我们考虑将 pi 置零后可以得到一组最小费用可行流，则可以直接将初始的 pi 看做修改。
若将初始的 pi 排序，则维护最短路时可以用队列替换堆。
修改的做法和解法 1 一致，所以其实还是需要堆的。
特殊图
「洛谷 P1484」种树
考虑第 i 个间隔是 (i,i+1)，种一棵树相当于匹配相邻两个间隔。于是将第奇数个间隔连向第偶数个间隔容易构造费用流模型。
（但感觉其实这个图应该少了两条边）
注意到增广路等价于选取一段以空开头、结尾，空与树交错的区间并取反。
可以用链表维护极长的这样的段，用堆维护决策。
「BZOJ4877」跳伞求生
不妨将问题抽象成老鼠进洞，每个老鼠和洞都有费用。本题老鼠与洞在单向链上。
解法 1
考虑模拟 EK，那么增广路要么是正向，要么是反向。
不妨用线段树维护单向链上的流量和增广路。正向增广路只需是区间内最优的可以匹配的老鼠 → 洞，而反向增广路需是区间内可流且最优的可以匹配的老鼠 ← 洞。
维护 >0 的信息可以转化为维护 > 区间流量 min 的信息。
解法 2
也可以不模拟 EK，考虑以任意顺序加入老鼠和洞。
只需要额外维护负环即可，其意义是反向选择一个已经匹配的同类点做反悔。增广路仍然是正向选择一个未匹配的点匹配。
用线段树维护可流的区间，相较上一解法要容易许多。
解法 3
注意到如果我们沿着边的方向加入老鼠和洞，则线段树可以直接换成堆。
「PA2013」Raper / 「CF802O」April Fools' Problem (hard)
解法 0
WQS 二分后应用上一题的任意解法。
解法 1
应用上一题的解法 1。
解法 2, 3
应用上一题的解法 2, 3。则此时需要考虑完全反悔一组匹配，另外维护即可。
「CF280D」k-Maximum Subsequence Sum
注意到此问题仍然属于老鼠进洞，但链上的容量限制为 1。
模拟 EK。考虑当前有一些边被取反，而增广路要么是正向，要么是反向。因此，事实上我们只会做两种决策：
新增一段。
将已选的一段分裂成恰好两段。
那么我们可以对于选择和未选择的部分分别维护最大子段和。
事实上，我们也可以直接维护整个序列的最大子段和，选择时将子段和乘 −1。因为考虑若选择的子段不属于以上两种决策，那么就意味着出现了正环，这是与 EK 算法矛盾的。
「ckw 论文题」贸易
区间询问，考虑猫树分治。用可持久化数据结构维护两侧的后缀与前缀残量网络，三分中边的流量。
「全国統一プログラミング王決定戦本戦」Homework Scheduling
对每个任务建点 P1,…,PN，对每天建点 Q1,…,QN。建图：
对于 i=1,…,N，连边 (Pi,QAi,1,Xi),(Pi,QN,1,Yi)。
对于 i=1,…,N−1，连边 (Qi+1,Qi,∞,0)。
对于 i=1,…,N，连边 (S,Pi,1,0),(Qi,T,1,0)。
考虑逐个加入 (Qi,T) 的边，由于 Xi>Yi，因此不存在正环，只需考虑从 S 向 Qi 增广。
注意到增广路至多经过两个任务点。若需要从左往右流，需要区间内的反向边容量为正。
可以用线段树维护反向边容量，不过在叶子可能需要堆。
「NOI2017」蔬菜
不妨假设第 i 种菜有一棵特殊的菜在 ⌈xici⌉ 天变质，费用为 si+ai。
解法 1
套用上一题的做法，此时增广路只可能经过一个菜点，因而更加简单。
解法 2
注意到我们可以把「只在前 p 天卖菜」改成「卖了不超过 pm 棵菜」，这样可以按流量模拟。
套用先前老鼠进洞的诸多做法即可。由于其中一边费用为 0，容易将复杂度瓶颈上的 logn 换成 α(n)。
「ckw 论文题」双向链
解法 1
考虑先加入所有洞，然后从左往右加入老鼠。
注意到往右匹配时不会经过反向边（因为不存在从右往左的匹配），往左匹配时可能会经过反向边。并且注意到加入 i 之后，i 左侧的边的反向流量不会增加，因此每条边的费用只会修改 O(1) 次。
因此还是可以线段树维护。
解法 2
记 si,ti 表示 x1,…,i−1,y1,…,i−1 的和，vi,wi 表示第 i 个老鼠和洞的费用。
建点 X1,X2,…,Xn 和 Y1,Y2,…,Yn。然后考虑一个与原建模等价的图：
对 i=1,…,n−1，连边 (Xi,Xi+1,∞,0)。
对 i=1,…,n−1，连边 (Yi+1,Yi,∞,0)。
对 i=1,…,n，连边 (S,Xi,1,vi−si)，(Yi,T,1,wi−ti)，(Xi,Yi,∞,si+ti)。
那么我们从左往右考虑，每次考虑流过 (Xi,Yi) 这条边的流量。虽然同时有增广路和负环，但是我们可以维护两个堆，一个记录可以流到 Xi 的路径，另一个记录可以流出 Yi 后可行的路径。
事实上可以证明，我们每一次只需要考虑 (S,Xi),(Yi,T) 的边以及每次尝试匹配后形成的反悔路，而不会凭空出现其他路径。这比较符合直觉，但网络上证明较少，一个例子是 qyc 留下的结果。
类似的题目还有「UER #8」雪灾与外卖、「IOI2017」Wiring，以及更强的「CTSC2010」产品销售。前两题的做法基本没有变化，第三题堆做法将失效，但可以注意到每次加入的反悔路都会在堆顶，因此可以用平衡树统一执行 push 和 pop。
「省选联考 2023」人员调度
对每个部门建点 P1,…,Pn，建图：
对 i=2,…,n，连边 (Ppi,Pi,∞,0)。
对 i=1,…,k，连边 (S,Pxi,1,vi)。
对 i=1,…,n，连边 (Pi,T,1,0)。
考虑以任意顺序加入代表优秀员工的边，这样可以连带修改一并处理（先不考虑删除）。
那么需要考虑增广路和正环，注意到只需先尝试向上走到最浅的能够到达的祖先，其子树内的所有点都是可以走到的。因此是容易维护的。
考虑删除的话，本题的常见解法是直接线段树分治。也存在维护退流的做法，参见下一题。
「LNR #2」黄金矿工
树边的费用可以差分到矿工和黄金上。于是建图与上一题一致。注意到上一题中需要退流一个矿工，等价于添加一个费用相反的黄金。
正环与增广路的结构是本质相同的，我们考虑视作树上有向路径，其中向上的部分需要反向边容量为正。可以用动态树分治维护，标算是链分治，也就是树链剖分然后用堆维护轻子树并用线段树等维护区间最值。
「2018 ICPC World Finals」Conquer The World
解法 1
将双向链的线段树做法直接上树，注意到按照 DFS 序加一侧边仍然可以维持反向边切换次数为 O(1)。
解法 2
将双向链的堆做法换成可并堆即可。