CF802N/O

ywli08 · 2025-10-13 13:45:57 · 题解

10.13 模拟赛T3。
费用流的做法显然：建立超级源点 S 与 超级汇点 T，a, b 两序列对应的点分别称为 A_i, B_i，按以下方式连边：

• S \xrightarrow{1, a_i} A_i
• B_i \xrightarrow{1, b_i} T
• A_i \xrightarrow{1, 0} B_j, \forall i < j

但是由于数据范围和时间限制，即使加上优化建图也跑不过去。

还是从最小费用最大流的角度思考。注意到流的最小费用关于流的大小是一个凸函数。于是可以 wqs二分。判定可以用反悔贪心。