题目：洛谷P1525、Vijos P1776、codevs1069。

题目大意：有一些罪犯，两个罪犯之间可能会发生冲突，冲突有个影响力，而如果两个罪犯在不同监狱里，就可以避免冲突。现在有两个监狱，要你安排一种关押罪犯的方式，使得影响力最大的一次冲突影响力最小。

解题思路：贪心+并查集。先将所有冲突按影响力从大到小排序，然后一件一件处理，用并查集储存哪些罪犯处于同一个监狱中。我们把每个罪犯变成两个，如果该罪犯原来编号为$i$，那么现在编号为$2i$和$2i-1$，如果$2i$和$2j-1$处于同一个并查集内，则说明$i$和$j$关在不同的监狱里。如果两个罪犯已经在同一监狱里，则根据贪心的原则，该影响力就是答案。

注意题目说的如果没有冲突，输出0。

注意代码第24行和25行的合并操作。

C++ Code：

 

#include
     
      #include
      
       using namespace std;int n,m;struct edge{	int u,v,dis;	bool operator <(const edge&rhs)const{return dis>rhs.dis;}}e[100005];int fa[40004];int dad(int x){	return x==fa[x]?x:fa[x]=dad(fa[x]);}int main(){	scanf("%d%d",&n,&m);	for(int i=1;i<=m;++i)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].dis);	sort(e+1,e+m+1);	for(int i=1;i<=2*n;++i)fa[i]=i;	for(int i=1;i<=m;++i){		int x=dad(2*e[i].u),y=dad(2*e[i].v);		if(x==y){			printf("%d\n",e[i].dis);			return 0;		}		fa[dad(2*e[i].u-1)]=y;		fa[x]=dad(e[i].v*2-1);	}	puts("0");	return 0;}