ARC125E 题解

在下文的叙述中，默认 $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)$。