[ARC125E] Snack 网络流

Nevertheless1437 · 2023-10-10 20:24:11 · 题解

考虑网络流。

记 (x, y, z) 为 x \to y 流量为 z。下文称 x 为零食， y 为小孩。

然后我们发现显然会 TLE，所以考虑最小割。

考虑断掉 y_i \to T 和 S \to y_i 哪个小，前者是 c_i。

然后就发现了断掉 S \to y_p 的路只需要断掉还没有断掉的那些 S \to x 的 (x, y, b_p) 即可。那么这个只跟这些 x 的个数有关，不难想到枚举 x 的个数。

那么考虑割掉 k 个 x，答案即为：

• 选取 k 个 a_x 割掉
• 加上 \sum \min(c_i,(n - k) \times b_i)

前面那个显然取 k 个最小的，后面那个可以按照 \frac{c_i}{b_i} 排序 + 双指针解决，想直接做的我是不是傻了 （）

复杂度线性对数。