[NOIp2010提高组]关押罪犯

OJ题号：洛谷1525

思路：贪心。

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

 #include<cstdio>
 #include<algorithm>
 #include<functional>
 struct Edge {
     int u,v,w;
     bool operator >(const Edge &x) const {
         return this->w>x.w;
     }
 };
 const int N=;
 class UnionFindSet {
     private:
         int anc[N<<];
         int Find(int x) {
             return (x==anc[x])?x:(anc[x]=Find(anc[x]));
         }
     public:
         UnionFindSet(const int n) {
             for(int i=;i<=n<<;i++) anc[i]=i;
         }
         bool isConnected(const int x,const int y) {
             return Find(x)==Find(y);
         }
         void Union(const int x,const int y) {
             anc[Find(x)]=Find(y);
         }
 };
 int main() {
     int n,m;
     scanf("%d%d",&n,&m);
     Edge e[m];
     for(int i=;i<m;i++) {
         scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
     }
     std::sort(&e[],&e[m],std::greater<Edge>());
     UnionFindSet s(n);
     for(int i=;i<m;i++) {
         if(s.isConnected(e[i].u,e[i].v)) {
             printf("%d\n",e[i].w);
             return ;
         }
         s.Union(e[i].u,e[i].v+n);
         s.Union(e[i].v,e[i].u+n);
     }
     puts("");
     return ;
 }