ARC125E 题解

shiruoyu114514 · 2025-05-11 20:43:35 · 题解

在下文的叙述中，默认 i 为小孩，j 为零食。

有一个显而易见的网络流：左部点为小孩，右部点为零食，S 向 i 连 c_i 大小的边，i 向 j 连 b_i 大小的边，j 向 T 连 a_j 大小的边。求最大流即可。时间复杂度 O(n^4)，过不了一点。

考虑最大流转最小割。不难发现对于任何一个 i，其要么断掉 S \rightarrow i 的边，要么对于每一个没有断掉 j \rightarrow T 的 j，断掉 i \rightarrow j。

由于每个 j 除了 a_j 不等外其余地位相等，考虑起来最简单，所以先从少到多枚举 j \rightarrow T 的断边。显然在给定断边条数的情况下，应该首先断最小的。

现在假设有 n_j 种零食。每个 i 要么断掉所有 j \rightarrow T 没有被断掉的 i \rightarrow j 边，消耗 b_in_j，要么断掉 S \rightarrow i 边，消耗 a_i。不难发现随着 n_j 的减小，i 的贡献会由 a_i 变成 b_in_j。在每次转折时维护即可。时间复杂度 O(n \log n)。