题解 P1525 【关押罪犯】
wuzhoupei
2017-09-23 07:04:20
总体来讲这是一个并查集的题，我们把模型抽象出来，就是一张无向图，要求按照条件将图中的点分成两部分，使得两个集合中的最大边最小
仔细想想，这是一道基于并查集的题，而且一定会把大的边割断使这条边不存在，只是一个小贪心，但是普通的并查集思想又不是很好做，所以我们有了以下分析：
既然是贪心，我们会根据边的大小来排序，由大到小排；
假设当前点线是A—B，则有以下几种情况：
<1> A，B都分别还没有在任何一个监狱中，所以我们这时候把A，B分别放入两个对立的监狱，至于对立的监狱的概念，我们为了方便代码实现，就定义任意一个监狱编号为X，则X^1为监狱X的对立监狱；
<2>A，B中有一个人A已经在监狱中了，而另一个人B没有，则我们把B放入A所在监狱的对立监狱；
<3>A，B都在监狱中，但两所监狱不是对立的，我们把A放在B目前的监狱的对立监狱，此时A的监狱编号已经改变，我们把原A所在的监狱的对立监狱的人放在现在B所在的监狱；
<4>A，B都在监狱中，且所在监狱相同，则这条边就是答案；
放监狱这个步骤就是并查集，排序是贪心，所以这道题是贪心+并查集；
我的博客： http://blog.csdn.net/pretend\_fal
完整代码：
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#define II int
#define R register
#define I 123456
using namespace std;
struct node {
II x,y;
II w;
}aa[I];
II fa[I];
II n,m,ans,_tot;
bool maP(node a1,node a2)
{
return a1.w>a2.w;
}
II find(R II x)
{
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
int main()
{
scanf("%d%d",&n,&m);
_tot=22001;
//监狱编号在>n时认为已经放到监狱中了
//所以，为了避免与初始状态重复，我们令最小的监狱编号为n范围之外
for(R II i=1;i<=40000;i++) fa[i]=i;
for(R II i=1;i<=m;i++) scanf("%d%d%d",&aa[i].x,&aa[i].y,&aa[i].w);
sort(aa+1,aa+m+1,maP);
ans=0;
for(R II i=1;i<=m;i++)
{
R II X=find(aa[i].x);
R II Y=find(aa[i].y);
if(X<=n&&Y<=n) fa[X]=++_tot,fa[Y]=++_tot;
//情况<1>；
else if(X<=n&&Y>n) fa[X]=fa[Y]^1;
//情况<2>之一；
else if(X>n&&Y<=n) fa[Y]=fa[X]^1;
//情况<2>之二；
else if(X>n&&Y>n){
if(X==Y) {
printf("%d\n",aa[i].w);
return 0;
}
//情况<4>;
if(X!=(Y^1)){
R II XXOR=X^1;
R II YXOR=Y^1;
fa[Y]=XXOR;
fa[YXOR]=X;
}
//情况<3>；
}
}
cout<<0<<endl;
return 0;
}
```