题目大意：
n个点，m条边，边权cj。将n个点分到两个集合中（集合均不能为空），使两个集合内的所有边的最大值最小，输出最小值。
样例输入：
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
样例输出：
3512
样例解释：
A集合：1 4；
B集合：2 3；
集合内边权最大值为3512.
数据范围：
对于100%的数据有N<=20000，M<=100000.//毕竟NOIP. %%%%%
解题思路：
NOIP2010……第一眼，这题怎么这么水！这题也叫NOIP？
我觉得我可以不开屏幕拿省队了，，上天上天。。
……
……
……
三小时后我觉得自己就是个烧饼……还有他也是@YOUSIKI
其实此题有两种解法：二分图染色or并查集。
在这里说一说二分图染色吧。
先把所有边按边权排个序，记录两个端点（struct），然后二分边的编号，由于要求最大边的最小值，显然我们从大到小加入边的这一行为是满足二分性质的（神犇zrt的教诲）。每次二分判断是否可行，只需将图01染色（同一条边的两个端点一个标0一个标1），出现矛盾说明不是二分图，即不能满足将这些点分到两个集合中，继续二分即可。
注：
- 染色时dfs or bfs皆可，但一定要搞成bool型，以便及时返回，否则T一年。
- 染色时不要忘了开father数组，防止在两个点之间来回走，再次T一年。
- 存反向边。
- 每次二分边的条数时重新存图，比直接存一个图再判断要快，为什么？不知道。
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
struct N{
int head;
int ver;
int val;
friend bool operator < (N aaa,N bbb){
return aaa.val>bbb.val;
}
}aa[100005];
const int dian=20005;
const int bian=100005;
int n,m,ans;
int head[dian],next[bian],ver[bian],vis[dian];
bool dfs(int s,int fa){
for(int i=head[s];i!=-1;i=next[i]){
int x=ver[i];
if(x==fa)
continue;
bool v=vis[s];
if(vis[x]==-1){
if(v){
vis[x]=0;
if(!dfs(x,s))
return false;
}
else{
vis[x]=1;
if(!dfs(x,s))
return false;
}
}
else if(v==vis[x])
return false;
}
return true;
}
bool pd(int a){
int tot=0;
memset(vis,-1,sizeof(vis));
memset(next,-1,sizeof(next));
memset(head,-1,sizeof(head));
for(int i=1;i<=a;i++){
tot++;
ver[tot]=aa[i].ver;
next[tot]=head[aa[i].head];
head[aa[i].head]=tot;
tot++;
ver[tot]=aa[i].head;
next[tot]=head[aa[i].ver];
head[aa[i].ver]=tot;
}
for(int i=1;i<=n;i++){
if(vis[i]==-1){
vis[i]=0;
if(!dfs(i,-1))
return false;
}
}
return true;
}
void ef(int l,int r){
if(l>r){
return;
}
int mid=(l+r)/2;
if(pd(mid)){
ef(mid+1,r);
}
else{
ans=mid;
ef(l,mid-1);
}
}
int main(){
int a,b,c,tot=0;
cin>>n>>m;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
aa[i].head=a;
aa[i].ver=b;
aa[i].val=c;
}
sort(aa+1,aa+m+1);
ef(1,m);
if(ans==m)
printf("0");
else
printf("%d",aa[ans].val);
return 0;
}NOIP %%%%%