CF789E The Great Mixing 题解

我们给每一杯可乐先乘上 让其变成整数。

我们希望构造 ，并且要最小化 。

特判 的情况。考虑把 乘到右边去，得到

移项得到

我们另 表示这个 。我们希望用最小的 让 到达 。我们每选择一个物品，就会让 增加 。

我们对于每个 建出点来，对于每个 ，从 向 连边。我们实际上要找出原图的一个最小环。对于每个 可达的点作为源点跑多源 BFS 即可。

对于任意一组可行解，我们可以构造一组重排方案使得每个前缀和都在 中。这是 Steinitz 定理所保证的内容。