Description
S城现有两座*，一共关押着N名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c的罪犯被关押在同一*，他们俩之间会发生摩擦，并造成影响力为c的冲突事件。
每年年末，警察局会将本年内*中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S城Z市长那里。公务繁忙的Z市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。在详细考察了N名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座*内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一*内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使Z市长看到的那个冲突事件的影响力最小？这个最小值是多少？
Input
第一行为两个正整数N和M（N≤20000，M≤100000），分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的M行每行为三个正整数a[j]，b[j]，c[j]，表示a[j]号和b[j]号罪犯之间存在仇恨，其怨气值为c[j]。数据保证1≤a[j]。
Output
共1行，为Z市长看到的那个冲突事件的影响力。如果*中未发生任何冲突事件，请输出0。
Hint
对于30%的数据有N<=15。 对于70%的数据有N<=2000,M<=50000。 对于100%的数据有N<=20000,M<=100000。
Solution
并查集结合了贪心。用一个elm数组标记敌人，如果已经找到了elm就要把另一个dounion一下，更新他们的父亲为一样的，如果他们的父亲已经是一样的就需要输出了，这个时候的贪心策略就很显然，把所有的关系按照从大到小排序，如果遇到了父亲一样的就一定是最小的最大值了。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 200005
using namespace std;
struct data{
int a;
int b;
int f;
friend bool operator < (data a,data b){
return a.f>b.f;
}
}cm[maxn];
int FA[maxn],elm[maxn];
int n,m;
int dofind(int x){
if(FA[x]==x)return x;
return FA[x]=dofind(FA[x]);
}
void dounion(int x,int y){
int dx=dofind(x),dy=dofind(y);
if(dx!=dy){
FA[dx]=FA[dy];
}
}
bool dofinD(int x,int y){
return dofind(x)==dofind(y);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&cm[i].a,&cm[i].b,&cm[i].f);
}
for(int i=1;i<=n;i++){
FA[i]=i;
}
sort(cm+1,cm+m+1);
for(int i=1;i<=m+1;i++){
if(dofinD(cm[i].a,cm[i].b)){
printf("%d\n",cm[i].f);
return 0;
}
else{
if(!elm[cm[i].a]){
elm[cm[i].a]=cm[i].b;
}
else dounion(elm[cm[i].a],cm[i].b);
if(!elm[cm[i].b]){
elm[cm[i].b]=cm[i].a;
}
else dounion(elm[cm[i].b],cm[i].a);
}
}
return 0;
}