？
by Aria_Math @ 2024-04-19 19:50:45
就是 CF1430G
by forest114514 @ 2024-04-19 19:58:19
@[Aria_Math](/user/409327) @[call_of_silence](/user/1168861) @[Maleatas](/user/756786) 请不要发表无意义言论
by Biome_Fest @ 2024-04-19 20:01:23
@[forest114514](/user/320449) 但CF1430G 不是切糕模型吗
by Maleatas @ 2024-04-19 20:01:45
@[Maleatas](/user/756786) 我知道虽然这题我也想出了普通最小割切糕模型的做法但这种做法跑 dinic 点数和边数都是 $O(N^2)$ 的，如果能把 $>$ 的条件转化为 $\geq$ 条件就能加起来就能用保序回归来做，只用跑 $O(\log N)$ 次边数和点数都是 $O(N)$ 的 dinic，在数据更大的时候薄纱前者。
by forest114514 @ 2024-04-19 20:03:14
@[forest114514](/user/320449) $O(n)$级别的边数与点数的建图还是可以做的吧，但是孩子还小，不理解什么保序回归\ke\ke
by call_of_silence @ 2024-04-19 20:11:51
$O(n^2)$的输出方案的时候非常爽啊
by call_of_silence @ 2024-04-19 20:13:54
我只是想探究探究更优的做法，我还是觉得虽然网络流常数极小但 $O(N^3 \log N)$ 应该比 $O(N^6)$ 跑得快很多吧，至于什么是保序回归请见 [P6621 [省选联考 2020 A 卷] 魔法商店](https://www.luogu.com.cn/problem/P6621)
by forest114514 @ 2024-04-19 20:15:43
P6621 [省选联考 2020 A 卷] 魔法商店 的部分分做法就是 CF1430G 的那种切糕模型 @[call_of_silence](/user/1168861)
by forest114514 @ 2024-04-19 20:16:58
@[forest114514](/user/320449) 如何评价$O(n)$级别的点数和边数$O(n^2)$被拉爆
by call_of_silence @ 2024-04-19 21:13:38