题目传送门
感想：相信自己的想法！继续挖掘！
读完题目后：看到的最大值最小？二分答案啊！再仔细一看：wi达到了1e9，二分可能费点劲。（其实真的是可以的）而且check函数貌似并没有什么行之有效的写法。继续往下想。
再读读，想到我们肯定尽量不想让有仇恨的犯人关在一起，所以每次就把有仇的敌人用并查集并在一起（其实想法是挺好的，到这一步出现了偏差）。
结果...然后就没有结果了！
唉其实应该自己再多想想的嘛...还是去看了@Chemist和@new2zy两位巨佬的题解。主要有两种方法。
法一：二分图+二分答案
这题很好的满足了二分图的性质。是不错的二分图例题。
给出二分图定义：若无向图的n个节点可分为A,B两个非空集合，且A,B的交集为空集，且同一集合内的点没有边相连，称这种图为二分图。
二分图判定定理：一张无向图是二分图，当且仅当它不存在奇环。
代码实现：染色法。用黑白来标记图中两种节点，用大法师（Dfs）或绑发饰（Bfs）实现，遍历每条边如果没被访问，就染相反的颜色，否则判断它已染的色是否不合法。（根据定义，一个节点被标记后，它所有的相邻节点颜色应与他不同）。
get了这个知识，我们可以与最初的想法二分答案结合，本题中一个合法解需满足存在二分图的情况，而最优解可以通过二分实现。那么判断是否为二分图就成为了check函数的内核。
Code
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue> using namespace std; int n,m,tot,l,r;
int head[],vis[];
struct node{
int to,next,val;
}edge[]; void add(int x,int y,int z)
{
edge[++tot].to=y;
edge[tot].val=z;
edge[tot].next=head[x];
head[x]=tot;
} bool check(int w)
{
memset(vis,,sizeof(vis));
queue<int>q;
for(int k=;k<=n;k++)
if(!vis[k])
{
q.push(k);vis[k]=;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];i;i=edge[i].next)
if(edge[i].val>=w)
{
int y=edge[i].to;
if(!vis[y]) vis[y]=-vis[x],q.push(y);
else if(vis[y]==vis[x]) return false;
}
}
}
return true;
} int main()
{
scanf("%d%d",&n,&m);
// l=1;
for(int i=;i<=m;i++)
{
int a=,b=,c=;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
r=max(r,c);
}//r++;
while(l<r)
{
int mid=(l+r+)>>;
if(check(mid)) r=mid-;
else l=mid;
}
printf("%d",l);
return ;
}
*代码细节注意：入队地点（没被访问过），二分细节。
法二：冰茶几+略微贪心思想
由于Chemist大神已经讲的十分清楚，我就少发表些拙见。（扔下地址跑）
我们当然可以贪心地把仇恨值从大到小排序，先使仇恨值大的几对罪犯分到两个监狱，再秉承《团伙》一题中“敌人的敌人就是朋友”的观念，如果实在分不开了，当前的就是答案。
现在这么优质的一题多解的noip题已经很难找了。好题！好题！
