题目描述
S 城现有两座*，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极
不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨
气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之
间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一*，他们俩之间会发生摩擦，并
造成影响力为c 的冲突事件。
每年年末，警察局会将本年内*中的所有冲突事件按影响力从大到小排成一个列表，
然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力，
如果影响很坏，他就会考虑撤换警察局长。
在详细考察了N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在
两座*内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只
要处于同一*内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那
么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是少？
输入描述
第一行为两个正整数N 和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。
接下来的M 行每行为三个正整数aj，bj，cj，表示aj 号和bj 号罪犯之间存在仇恨，其怨气值为cj。数据保证，且每对罪犯组合只出现一次
输出描述
共1 行，为Z 市长看到的那个冲突事件的影响力。如果本年内*
中未发生任何冲突事件，请输出0
样例输入 Sample Input
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
样例输出
3512
【数据范围】
对于30%的数据有N≤ 15。
对于70%的数据有N≤ 2000，M≤ 50000。
对于100%的数据有N≤ 20000，M≤ 100000。
核心程序
for(i=1;i<m+1;i++)
{
sa=find(crime[i].a);
sb=find(crime[i].b);
if(sa==sb)
{
ans=i;
break;
}
else
{
f[sa]=f[find(crime[i].b+n)];
f[sb]=f[find(crime[i].a+n)];
}
}
数据结构分析：树形结构（二叉）
结构体：
typedef struct
{
int a,b,anger;
}Node;
算法：并查集（树形），运用递归实现。
思路：先给“怨气值”进行排序。
然后找最大的“怨气值”，把对应的两人分到两所*去。
再找次大的“怨气值”：（对应的两个人这时有三种情况）
1其中已经有一个人分好了*：另一个人分到另一个*。
2两个人甲乙都还没分好*：找与甲乙有怨的已经在*里的所有人，发现其中与甲最怨的是丙，与乙最怨的是丁，找出丙丁中更怨（最怨、更怨：排序顺序靠近大的一段）一点的丙，发现丙在狱1，果断把甲放到狱2，乙放到狱1。
3两个人的*都分好了：（又分两种情况）
1)两个人不同*：OK不用分了
2)两个人同一个*：看来这俩会是最大的冤家（“最终结果”求出）
【若本次没有得出“最终结果”，反复执行第3步】
#include<stdio.h>
typedef struct
{
int a,b,anger;
}Node;
int n,m,ans;
int f[40002];
Node crime[100001];
void qsort(int l,int r)
{
int i=l,j=r,mid=crime[(i+j)/2].anger;
while(i<=j)
{
while(crime[i].anger>mid) i++;
while(crime[j].anger<mid) j--;
if(i<=j)
{
Node t=crime[i];
crime[i]=crime[j];
crime[j]=t;
i++;
j--;
}
}
if(i<r) qsort(i,r);
if(j>l) qsort(l,j);
}
int find(int x)
{
if(x!=f[x])
f[x]=find(f[x]);
return f[x];
}
int main()
{ int n,m,i,j,sa,sb;
scanf("%d%d",&n,&m);
for(i=1;i<m;i++)
scanf("%d%d%d",&crime[i].a,&crime[i].b,&crime[i].anger);
qsort(1,m);
for(i=1;i<=2*n;i++)
f[i]=i;
for(i=1;i<m+1;i++)
{
sa=find(crime[i].a);
sb=find(crime[i].b);
if(sa==sb)
{
ans=i;
break;
}
else
{
f[sa]=f[find(crime[i].b+n)];
f[sb]=f[find(crime[i].a+n)];
}
}
printf("%d",crime[ans].anger);
return 0;
}