题解：AT_arc125_e [ARC125E] Snack
q1uple
·
·
题解
好好好！！！上课的例题喵。
首先这个东西我们可以网络流。我们从源点项每一种零食连一个容量为 a_i 的边。每一种零食在向小孩连容量为 b_i 的边。每一个小孩向汇点连容量为 c_i 的边。跑最大流即可，但是显然过不了。我们知道最大流是等于最小割的，我们转换成为最小割，我们先假设已经删去了 a_i 那一边的东西，所以我们先考虑后面那一坨东西，那么后面的贡献就是
\sum\limits_{i}{ \min(b_i x,c_i) }
其中 x 是剩余集合大小，而已经用过的正是前面 a_i 的部分。我们贪心的想，我们 a_i 取越小的越优，直接排序即可。
而后面的部分，我们注意到当且仅当 x \leq \frac{c_i}{b_i}，才能取到前面，枚举的时候把当前的贡献加上或减掉就行了。
submission