OJ题号：洛谷1525

思路：贪心。

先将所有的人按怨气值从大到小排一下，然后依次尝试将双方分入两个不同的监狱，如果失败（即已分入相同的监狱），则输出这个怨气值。

1 #include
     
       2 #include
      
        3 #include
       
         4 struct Edge { 5     int u,v,w; 6     bool operator >(const Edge &x) const { 7         return this->w>x.w; 8     } 9 };10 const int N=20001;11 class UnionFindSet {12     private:13         int anc[N<<1];14         int Find(int x) {15             return (x==anc[x])?x:(anc[x]=Find(anc[x]));16         }17     public:18         UnionFindSet(const int n) {19             for(int i=1;i<=n<<1;i++) anc[i]=i;20         }21         bool isConnected(const int x,const int y) {22             return Find(x)==Find(y);23         }24         void Union(const int x,const int y) {25             anc[Find(x)]=Find(y);26         }27 };28 int main() {29     int n,m;30     scanf("%d%d",&n,&m);31     Edge e[m];32     for(int i=0;i
        
         ());36     UnionFindSet s(n);37     for(int i=0;i