求noip2010第三题关押罪犯并差集解法

发布网友发布时间：2023-09-25 17:05

共3个回答

热心网友时间：2024-11-07 17:58

首先，将怨恨值由大到小排序，对于每个犯人建立为一个独立的集合，对立集合设为空集。由大到小依次按如下方法合并怨恨值所表示的两点：如果属于同一集合则输出这个值，否则依次与另一个点的对立集合合并，注意空集情况！复杂度O(m*log(m))
根本不用二分答案！！！
但是你如果就是喜欢二分答案我建议你二分答案+BFS二分图判定。复杂度O(m*log(10^9))

热心网友时间：2024-11-07 17:58

用二分答案+并查集做。
首先将题目所给的冲突值进行排序，再可以对答案所在的区间进行二分。
定区间为[l，r]，设答案为ans=（l+r）div 2。如果现在找的答案符合条件，即比第ans个冲突值大的边可以分在两个集合中，而这两个集合中的人的互相的冲突值都比ans的值小。就可以将答案的上限缩小，再进行二分。如果不符合条件，即即比第ans个冲突值大的边可以分在两个集合中，而这两个集合中的人的冲突值有比ans的值大的，就可以把下界缩小。当l〉=r时就可以的出答案为ans。
那么如何确定条件呢？我们可以用并查集实现。
以每条边的两点互为父结点，设一个关系为他们是否在同一集合中。
每次选边时判断这两条边的点（包括以这点为父结点的点）的关系。
用并查集来判断就可以完全解决了。

热心网友时间：2024-11-07 17:59

贪心选取，用并查集判读连通性

求noip2010第三题关押罪犯 并差集解法

求noip2010第三题关押罪犯并差集解法