- 关键点
- 特殊图
\((u, v, c, w)\) 表示 \(u \to v\)，容量 \(c\)，费用 \(w\)。
一般用最大 / 小费用可行流模型。
注意基本事实：EK 不会出现负环，因而不会退掉 \(S, T\) 的邻边。
关键点
「AGC018C」Coins
注意到一共恰有 \(X+Y+Z\) 个人，令 \(N=X+Y+Z\)，因而可以首先假定每个人都选择金币，再用费用流调整。
对每个人建点 \(P_1, \dots, P_N\)，对每一组建点 \(F_1, F_2\)。
对于 \(i=1,\dots,N\)，连边 \((P_i, F_1, 1, B_i), (P_i, F_2, 1, C_i)\)。
对于 \(i=1,\dots,N\)，连边 \((S, P_i, 1, -A_i)\)。
连边 \((F_1, T, Y, \infty), (F_2, T, Z, \infty)\)。
以 \(S, F_{1, 2}, T\) 为关键点，讨论两两之间（不经过其他关键点）的最短路：
\(S \to F_1\)：将一个选择金币的人 \(i\) 改为选择银币，费用为 \(B_i - A_i\)。
\(S \to F_2\)：将一个选择金币的人 \(i\) 改为选择铜币，费用为 \(C_i - A_i\)。
\(F_1 \to F_2\)：将一个选择银币的人 \(i\) 改为选择铜币，费用为 \(C_i - B_i\)。
\(F_2 \to F_1\)：将一个选择铜币的人 \(i\) 改为选择银币，费用为 \(B_i - C_i\)。
从而一条增广路也有四种形态。用堆维护即可。
「AGC034D」Manhattan Max Matching
注意到最大 Manhattan 距离可以直接拆符号，从 \(4\) 种可能的符号中取 \(\max\)。
对每个红点建点 \(R_1, \dots, R_N\)，对每个蓝点建点 \(B_1, \dots, B_N\)，对每一种符号建点 \(F_1, F_2, F_3, F_4\)。
对于 \(i = 1,\dots,N\)，连边 \((S, R_i, RC_i, \infty), (B_i, T, BC_i, \infty)\)。
对于 \(i = 1,\dots,N\)，连边 \((R_i, F_1, \infty, RX_i+RY_i), (F_1, B_i, \infty, -BX_i-BY_i)\)。
对于 \(i = 1,\dots,N\)，连边 \((R_i, F_2, \infty, RX_i-RY_i), (F_2, B_i, \infty, -BX_i+BY_i)\)。
对于 \(i = 1,\dots,N\)，连边 \((R_i, F_3, \infty, -RX_i+RY_i), (F_3, B_i, \infty, BX_i-BY_i)\)。
对于 \(i = 1,\dots,N\)，连边 \((R_i, F_4, \infty, -RX_i-RY_i), (F_4, B_i, \infty, BX_i+BY_i)\)。
以 \(S, F_{1, 2, 3, 4}, T\) 为关键点，讨论两两之间（不经过其他关键点）的最短路：
\(S \to F_j\)：为一个未匹配的红点选择第 \(j\) 种符号。
\(F_j \to T\)：为一个未匹配的蓝点选择第 \(j\) 种符号。
\(F_j \to F_k\)：将一个选择第 \(j\) 种符号的红点改成选择第 \(k\) 种符号，或将一个选择第 \(k\) 种符号的蓝点改成选择第 \(j\) 种符号。
「2019 ICPC Asia Shanghai Regional」Blood Pressure Game
\(b_j\) 匹配 \((i, i+1)\) 的费用是 \(|a_i-b_j|+|a_{i+1}-b_j|-|a_i-a_{i+1}|\)，最后那一项是已经确定的，前两项可以类似上一题直接拆符号，因此和上一题一样做即可。
「NOI2019」序列
解法 1
考虑到容量是个 \(\le\) 的限制，因此我们不妨改写成只能选择最多 \(k-L\) 种不同下标的匹配。
对每个位置建点 \(A_i, B_i\)，建中转点 \(U, V, T'\)。
对 \(i = 1,\dots,n\)，连边 \((S, A_i, 1, a_i), (B_i, T', 1, b_i)\)。
对 \(i = 1,\dots,n\)，连边 \((A_i, B_i, 1, 0)\)。
对 \(i = 1,\dots,n\)，连边 \((A_i, U, 1, 0), (V, B_i, 1, 0)\)。
连边 \((U, V, k-L, 0), (T', T, k, \infty)\)。
以 \(S, U, V, T\) 作为关键点，讨论两两之间（不经过其他关键点）的最短路：
\(S \to T\)：匹配一组两边都未匹配的 \((a_i, b_i)\)，费用为 \(a_i+b_i\)。
\(S \to U\)：选择一个未匹配的 \(a_i\)，费用为 \(a_i\)。
\(V \to T\)：选择一个未匹配的 \(b_i\)，费用为 \(b_i\)。
\(S \to V\)：选择一组 \((a_i, b_i)\)，其中 \(a_i\) 未匹配，\(b_i\) 已经过 \(V\) 匹配，费用为 \(a_i\)。
\(U \to T\)：选择一组 \((a_i, b_i)\)，其中 \(b_i\) 未匹配，\(a_i\) 已经过 \(U\) 匹配，费用为 \(b_i\)。
\(U \to V\)：直接经过这条边匹配，费用为 \(0\)；或是将经过 \(U, V\) 匹配的一组 \((a_i, b_j)\) 换成直接匹配，要求 \(i=j\)，事实上不存在这种情况。
\(V \to U\)：反悔一组经过这条边的匹配，费用为 \(0\)；或是将一组 \((a_i, b_i)\) 改为经过 \(U, V\) 匹配，事实上也不存在这种情况。
解法 2
考虑不观察直接硬做，将匹配的位置划分为三种：出现在 \(\{c_i\}\) 中，出现在 \(\{d_i\}\) 中，同时出现在两侧。
对每个下标建点 \(P_1, \dots, P_n\)，对每一种下标建点 \(F_1, F_2, F_3\)。
枚举第三种的数量为 \(p\)，建图：
对于 \(i=1,\dots,n\)，连边 \((P_i, F_1, 1, a_i), (P_i, F_2, 1, b_i), (P_i, F_3, 1, a_i+b_i)\)。
对于 \(i=1,\dots,n\)，连边 \((S, P_i, 1, 0)\)。
连边 \((F_1, T, k-p, \infty), (F_2, T, k-p, \infty), (F_3, T, p, \infty)\)。
最短路类似 Coins 一题，不再讨论。我们在增加 \(p\) 的时候会导致两条满流边容量减 \(1\)，一条满流边容量加 \(1\)。
不妨假设初始时存在 \((T, S, \infty, 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。因此我们对每个人建点 \(P_1, \dots, P_n\)，对每一队的四个角色建点 \(F_1, F_2, F_3, F_4\)。
由于队伍数不确定，考虑枚举队伍数 \(k\)，建图：
对于 \(i=1,\dots,n\)，连边 \((S, P_i, 1, p_i)\)。
对于 \(i=1,\dots,n\) 且 \(\texttt{`D'} \in S_i\)，连边 \((P_i, F_1, 1, 0)\)。
对于 \(i=1,\dots,n\) 且 \(\texttt{`S'} \in S_i\)，连边 \((P_i, F_2, 1, 0)\)。
对于 \(i=1,\dots,n\) 且 \(\texttt{`B'} \in S_i\)，连边 \((P_i, F_3, 1, 0)\)。
对于 \(i=1,\dots,n\) 且 \(\texttt{`D'} \in S_i \lor \texttt{`S'} \in S_i\)，连边 \((P_i, F_4, 1, 0)\)。
连边 \((F_1, T, k, -\infty), (F_2, T, k, -\infty), (F_3, T, k, -\infty), (F_4, T, k, -\infty)\)。
关键点显然是 \(S, F_{1, 2, 3, 4}, T\)，最短路部分类似前文，不再赘述。
\(k\) 增加时，由上一题的分析，只需要尝试从 \(S\) 到 \(F_j\) 增广。
修改时也要考虑退流。由于 \(T\) 的邻边均满流，只需要考虑消去不经过 \(T\) 的负环，即寻找一个 \(F_j\) 消去 \(S \to F_j \to S\) 的环。
解法 2
考虑先求出 \(k\)。可以将 \(p_i\) 置零后做模拟，也可以二分并使用 Hall 定理判定。
现在我们假设不存在任何 \((S, P_i)\) 边，然后按照 \(p_i\) 从小到大加入边。注意到不可能出现不经过 \(T\) 的负环，因此只需要考虑 \(S\) 到 \(T\) 的增广路。
修改的做法和解法 1 一致。
解法 3
我们考虑将 \(p_i\) 置零后可以得到一组最小费用可行流，则可以直接将初始的 \(p_i\) 看做修改。
若将初始的 \(p_i\) 排序，则维护最短路时可以用队列替换堆。
修改的做法和解法 1 一致，所以其实还是需要堆的。
特殊图
「洛谷 P1484」种树
考虑第 \(i\) 个间隔是 \((i, i+1)\)，种一棵树相当于匹配相邻两个间隔。于是将第奇数个间隔连向第偶数个间隔容易构造费用流模型。
（但感觉其实这个图应该少了两条边）
注意到增广路等价于选取一段以空开头、结尾，空与树交错的区间并取反。
可以用链表维护极长的这样的段，用堆维护决策。
「BZOJ4877」跳伞求生
不妨将问题抽象成老鼠进洞，每个老鼠和洞都有费用。本题老鼠与洞在单向链上。
解法 1
考虑模拟 EK，那么增广路要么是正向，要么是反向。
不妨用线段树维护单向链上的流量和增广路。正向增广路只需是区间内最优的可以匹配的老鼠 \(\to\) 洞，而反向增广路需是区间内可流且最优的可以匹配的老鼠 \(\gets\) 洞。
维护 \(> 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
对每个任务建点 \(P_1, \dots, P_N\)，对每天建点 \(Q_1, \dots, Q_N\)。建图：
对于 \(i=1,\dots,N\)，连边 \((P_i, Q_{A_i}, 1, X_i), (P_i, Q_N, 1, Y_i)\)。
对于 \(i=1,\dots,N-1\)，连边 \((Q_{i+1}, Q_i, \infty, 0)\)。
对于 \(i=1,\dots,N\)，连边 \((S, P_i, 1, 0), (Q_i, T, 1, 0)\)。
考虑逐个加入 \((Q_i, T)\) 的边，由于 \(X_i > Y_i\)，因此不存在正环，只需考虑从 \(S\) 向 \(Q_i\) 增广。
注意到增广路至多经过两个任务点。若需要从左往右流，需要区间内的反向边容量为正。
可以用线段树维护反向边容量，不过在叶子可能需要堆。
「NOI2017」蔬菜
不妨假设第 \(i\) 种菜有一棵特殊的菜在 \(\lceil\frac{x_i}{c_i}\rceil\) 天变质，费用为 \(s_i + a_i\)。
解法 1
套用上一题的做法，此时增广路只可能经过一个菜点，因而更加简单。
解法 2
注意到我们可以把「只在前 \(p\) 天卖菜」改成「卖了不超过 \(pm\) 棵菜」，这样可以按流量模拟。
套用先前老鼠进洞的诸多做法即可。由于其中一边费用为 \(0\)，容易将复杂度瓶颈上的 \(\log n\) 换成 \(\alpha(n)\)。
「ckw 论文题」双向链
解法 1
考虑先加入所有洞，然后从左往右加入老鼠。
注意到往右匹配时不会经过反向边（因为不存在从右往左的匹配），往左匹配时可能会经过反向边。并且注意到加入 \(i\) 之后，\(i\) 左侧的边的反向流量不会增加，因此每条边的费用只会修改 \(O(1)\) 次。
因此还是可以线段树维护。
解法 2
记 \(s_i, t_i\) 表示 \(x_{1,\dots,i-1}, y_{1,\dots,i-1}\) 的和，\(v_i, w_i\) 表示第 \(i\) 个老鼠和洞的费用。
建点 \(X_1, X_2, \dots, X_n\) 和 \(Y_1, Y_2, \dots, Y_n\)。然后考虑一个与原建模等价的图：
对 \(i=1,\dots,n-1\)，连边 \((X_i, X_{i+1}, \infty, 0)\)。
对 \(i=1,\dots,n-1\)，连边 \((Y_{i+1}, Y_i, \infty, 0)\)。
对 \(i=1,\dots,n\)，连边 \((S, X_i, 1, v_i-s_i)\)，\((Y_i, T, 1, w_i-t_i)\)，\((X_i, Y_i, \infty, s_i+t_i)\)。
那么我们从左往右考虑，每次考虑流过 \((X_i, Y_i)\) 这条边的流量。虽然同时有增广路和负环，但是我们可以维护两个堆，一个记录可以流到 \(X_i\) 的路径，另一个记录可以流出 \(Y_i\) 后可行的路径。
事实上可以证明，我们每一次只需要考虑 \((S, X_i), (Y_i, T)\) 的边以及每次尝试匹配后形成的反悔路，而不会凭空出现其他路径。这比较符合直觉，但网络上证明较少，一个例子是 qyc 留下的结果。
类似的题目还有「UER #8」雪灾与外卖、「IOI2017」Wiring，以及更强的「CTSC2010」产品销售。前两题的做法基本没有变化，第三题堆做法将失效，但可以注意到每次加入的反悔路都会在堆顶，因此可以用平衡树统一执行 push 和 pop。
「省选联考 2023」人员调度
对每个部门建点 \(P_1, \dots, P_n\)，建图：
对 \(i = 2,\dots,n\)，连边 \((P_{p_i}, P_i, \infty, 0)\)。
对 \(i = 1,\dots,k\)，连边 \((S, P_{x_i}, 1, v_i)\)。
对 \(i = 1,\dots,n\)，连边 \((P_i, T, 1, 0)\)。
考虑以任意顺序加入代表优秀员工的边，这样可以连带修改一并处理（先不考虑删除）。
那么需要考虑增广路和正环，注意到只需先尝试向上走到最浅的能够到达的祖先，其子树内的所有点都是可以走到的。因此是容易维护的。
考虑删除的话，本题的常见解法是直接线段树分治。也存在维护退流的做法，参见下一题。
「LNR #2」黄金矿工
树边的费用可以差分到矿工和黄金上。于是建图与上一题一致。注意到上一题中需要退流一个矿工，等价于添加一个费用相反的黄金。
正环与增广路的结构是本质相同的，我们考虑视作树上有向路径，其中向上的部分需要反向边容量为正。可以用动态树分治维护，标算是链分治，也就是树链剖分然后用堆维护轻子树并用线段树等维护区间最值。
「2018 ICPC World Finals」Conquer The World
解法 1
将双向链的线段树做法直接上树，注意到按照 DFS 序加一侧边仍然可以维持反向边切换次数为 \(O(1)\)。
解法 2
将双向链的堆做法换成可并堆即可。