并查集综合

种类并查集

关押罪犯

经典种类并查集。

考虑要想使最后的结果尽可能小，必须按照怨气值大小将每组关系排序，从大到小依次将罪犯放入监狱。

对于放的过程，用并查集维护。由于我们已经将怨气值大小排序，所以对于一组 \(a\) 与 \(b\) 的矛盾，将 \(a\) 与 \(b\) 不放在同一个监狱一定是最优的。用 \(to_i\) 代表 \(i\) 所在监狱的代表人物，起初，\(to_i=i\) 。如果 \(to_a\ne to_b\) ，代表 \(a\) 与 \(b\) 在前面的放置中不处在同一个监狱，于是我们可以将两人放在不同监狱中。

但是，我们注意到，如果将两人放在不同监狱中，那么在该操作前的操作中 \(b\) 的仇人，必然会跟 \(a\) 归为一个监狱（只有两个监狱），所以我们需要将所有出现的 \(b\) 的仇人放入 \(a\) 所在监狱。

于是，我们用 \(E_i\) 代表 \(i\) 的上一个出现的仇人，可以发现，对于所有已经出现过的 \(b\) 的仇人，他们一定都在同一个监狱（还是因为只有两个监狱）。我们可以将 \(to_{E_b}\) 与 \(to_a\) 合并，同理，将 \(to_{E_a}\) 与 \(to_a\) 合并。

注意，在操作过程中可能出现两人位于同一个监狱，但代表人物不一样，这并不妨碍我们。

可以感性的证明，在一次操作后罪犯分布合法。