codevs 1069 關押罪犯

看了題解，發現最好的方法是用并查集做（怎么自己就完全沒有想到這個算法呢？太嫩了啊- - ） 代碼：

解釋： 用并查集表示每個犯人之間的關系，在同一個集合中則說明兩人在同一個監獄，反之則不在同一個監獄。用類似于克魯斯卡爾的方法，先將邊排序，然后按照仇恨值的大小從大到小處理。對于每一組，先看兩個人能不能加入不同的集合， 如果可以，將兩人加入不同的集合，如果不可以，則輸出該組仇恨值。 用補集來表示兩個點不在一個集合中。如a和b’在同一個集合中，則a和b不在同一個集合中，不能把b直接加入另一個集合，因為會對后面的結果產生影響。 如，3和4不在同一個集合中，但是我們現在不知道究竟是3在第一個監獄還是4在第一個監獄，所以此時用3和4‘在同一個集合中來表示3和4不在同一個集合中。——轉載至http://blog.csdn.net/u013653310/article/details/46792373 自己的理解：（中午躺在床上半天終于想出來了），首先注意到有這條語句 int fx(find(dat[i].a)), fy(find(dat[i].b)); 說明fa[x]里面的x可能是（0 ~n,即本身），也可能是（x + n，即它的補集），所以先認清楚一個思維誤區，一個集合里面可能有(a+n , e+n，…)，他們的聯通塊編號可能是某個數字，比如(e+n)。在同一個集合里面，所有的正常數字不能和里面的某個補集，比如a+n共存，也就說，所有數字不能和a放在同一個集合。那么a + n 和 e+n 都在的話，說明什么呢？我們可以這樣想：既然所有數字都不能和a 一起， 也不能和e一起，而且又只有2個監獄，那么a 只能和 e一起。在這份代碼中，只要某2個數字得到的聯通快編號一樣，說明它們在同一個集合中，就不能再在同一個監獄中，所以就是不合法的了。