题目描述
S 城现有两座*，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一*，他们俩之间会发生摩擦，并造成影响力为c 的冲突事件。
每年年末，警察局会将本年内*中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
在详细考察了N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座*内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一*内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。
那么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？
输入输出格式
输入格式：
输入文件的每行中两个数之间用一个空格隔开。第一行为两个正整数N 和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的M 行每行为三个正整数aj，bj，cj，表示aj 号和bj 号罪犯之间存在仇恨，其怨气值为cj。数据保证1<aj=<=bj<=N ，0 < cj≤ 1,000,000,000，且每对罪犯组合只出现一次。
输出格式：
共1 行，为Z 市长看到的那个冲突事件的影响力。如果本年内*中未发生任何冲突事件，请输出0。
输入输出样例
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
3512
说明
【输入输出样例说明】罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是3512（由2 号和3 号罪犯引发）。其他任何分法都不会比这个分法更优。
![NOIP2010关押罪犯[并查集｜二分答案＋二分图染色 | 种类并查集]](https://image.shishitao.com:8440/aHR0cDovL2NkbnYyLmx1b2d1Lm9yZy91cGxvYWQvcGljLzI5OC5wbmc%3D.png?w=700&webp=1 "NOIP2010关押罪犯[并查集｜二分答案＋二分图染色 | 种类并查集]")
【数据范围】对于30%的数据有N≤ 15。对于70%的数据有N≤ 2000，M≤ 50000。对于100%的数据有N≤ 20000，M≤ 100000。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
并查集：
i的敌人集合为i+n，同一个敌人集合的人一定在同一个*
按怒气从大到小排序，依次考虑每对敌人，如果在同一个集合就输出，负责合并到对方的敌人集合里(因为是一个人的敌人)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=,M=;
int n,m,a,b,c,ans=;
struct edge{
int u,v,w;
}e[M];
int cnt=;
inline void add(int u,int v,int w){
cnt++;
e[cnt].u=u;e[cnt].v=v;e[cnt].w=w;e[cnt].u=u;
}
inline bool cmp(edge a,edge b){
return a.w>b.w;
}
int fa[N<<];
inline int findp(int x){
return x==fa[x]?x:fa[x]=findp(fa[x]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
sort(e+,e++m,cmp);
for(int i=;i<=n*;i++) fa[i]=i;
for(int i=;i<=m;i++){
int u=e[i].u,v=e[i].v,w=e[i].w;
int f1=findp(u),f2=findp(v);
if(f1==f2){ans=w;break;}
fa[f1]=findp(v+n);
fa[f2]=findp(u+n);
}
printf("%d",ans);
}
二分图：
二分最小c值，二染色看能不能成立，两种二染色方法
不知道为什么tle两个。。。。。原来是忘记m<<1了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=,M=;
int n,m,a,b,c,ans=;
struct edge{
int v,w,ne;
}e[M<<1];
int cnt=,h[N];
inline void ins(int u,int v,int w){
cnt++;
e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;
}
int col[N],W,w[M];
bool bi(int u){//printf("%d %d\n",u,col[u]);
for(int i=h[u];i;i=e[i].ne){
if(e[i].w<=W) continue;
int v=e[i].v;
if(col[u]==col[v]) return false;
if(!col[v]){
col[v]=-col[u];
if(!bi(v)) return false;
}
}
return true;
}
bool dfs(int u,int fa){
for(int i=h[u];i;i=e[i].ne){
if(e[i].w<=W) continue;
int v=e[i].v;
if(v==fa) continue;
if(col[u]==col[v]) return false;
if(!col[v]){
col[v]=-col[u];
if(!dfs(v,u)) return false;
}
}
return true;
}
bool check(){
for(int i=;i<=n;i++)
if(!col[i]){
col[i]=;
if(!bi(i)) return false;
}
return true;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
ins(a,b,c);w[i]=c;
}
sort(w+,w++m);
int l=,r=m;
while(l<r){
int m=(l+r)/; W=w[m];//printf("m %d %d\n",m,w[m]);
memset(col,,sizeof(col));
if(check()) ans=w[m],r=m;
else l=m+;
}
if(l==&&r<l) cout<<;
else printf("%d",ans);
}
[2016-10-31]
也可以用种类并查集，和POJ1703差不多，最快
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e4+,M=1e5+;
int n,m,a,b,c,ans=;
struct edge{
int u,v,w;
bool operator <(const edge &r)const{return w>r.w;}
}e[M];
int cnt=;
inline void add(int u,int v,int w){
cnt++;
e[cnt].u=u;e[cnt].v=v;e[cnt].w=w;e[cnt].u=u;
}
int fa[N],v[N];
inline int find(int x){
if(x==fa[x]) return x;
int root=find(fa[x]);
v[x]=(v[x]+v[fa[x]])&;
return fa[x]=root;
}
inline void unn(int a,int b){
int f1=find(a),f2=find(b);
if(f1!=f2){
fa[f1]=f2;
v[f1]=(v[a]+v[b]+)&;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
sort(e+,e++m);
for(int i=;i<=n;i++) fa[i]=i,v[i]=;
for(int i=;i<=m;i++){
int a=e[i].u,b=e[i].v,w=e[i].w;
int f1=find(a),f2=find(b);
if(f1==f2&&v[a]==v[b]){ans=w;break;}
unn(a,b);
}
printf("%d",ans);
}