最终形态一定是 \(n\) 个点形成的一个大环。
故每个点的入度一定为 \(1\)，我们考虑保留每个点入度中 \(c_i\) 最大的边，剩下的删除，此时原图一定变成一堆链加一些环。
对于环，我们是需要拆开的，此时我们可以枚举环上每个点，考虑将其反悔，反悔代价为环边代价减去其次大入边（最大入边一定为环边，才能保留），所以对于每个环找到其最小反悔代价即可。
需要特判初始就是大环的情况。时间复杂度 \(O(n)\).
拆分约束，将大环约束扔到每个点上。
loj2737. 「JOISC 2016 Day 3」电报
发布时间 2023-10-28 12:08:28作者: ydtz