【洛谷P1525】[NOIP2010]关押罪犯

关押罪犯

题目链接

思路：

二分图或并查集

这里讲并查集算法：

　　1.将每对罪犯的冲突关系按影响从大到小排序

　　2.将集合与（i+n）合并表示编号为i的罪犯不能在该集合内

　　3.依次从大到小处理冲突关系：

　　　　若x与y+n、y与x+n不在同一个集合内，将集合find(x)与集合find(y+n)合并，将集合find(x+n)与集合find(y)合并；

　　　　反之，则发生了冲突，退出循环，当前罪犯的怨气值即为最小的冲突影响

贴代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int n,m,fa[];

 int find(int x)

 {

     if(fa[x]!=x) fa[x]=find(fa[x]);

     return fa[x];

 }

 void unionn(int x,int y)

 {

     int fx=find(x),fy=find(y);

     fa[fx]=fy;

 }

 struct w{

     int l;

     int r;

     int data;

 } xw[];

 bool cmp(w x,w y)

 {

     return x.data>y.data;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=*n;i++)

     fa[i]=i;

     for(int i=;i<=m;i++)

     scanf("%d%d%d",&xw[i].l,&xw[i].r,&xw[i].data);

     sort(xw+,xw++m,cmp);

     for(int i=;i<=m;i++)

     {

         unionn(xw[i].l,xw[i].r+n);

         unionn(xw[i].l+n,xw[i].r);

         if(find(xw[i].l)==find(xw[i].l+n)||find(xw[i].r+n)==find(xw[i].r))    {

             printf("%d\n",xw[i].data);

             return ;

         }

     }

     cout<<<<endl;

     return ;

 }

@klxw