并查集做法

#include <algorithm>
#include <iostream>
using namespace std;
int n,m,f[40001],x,y;
struct data{int a,b,c;} e[100001];
bool gz(const data &a,const data &b) {return a.c > b.c;}
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
int main() 
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>e[i].a>>e[i].b>>e[i].c;
    for(int i=1;i<=n*2;i++)
        f[i]=i;//初始化 
    //有两个集 i友 与 i敌 用i+n表示
    sort(e+1,e+m+1,gz);//犯罪值降序 
    //因为要使最大冲突尽可能小，所以先分配大的(分离机会大) 
    for(int i=1;i<=m;i++) 
{
        x=find(e[i].a);//找自己的宗族 
        y=find(e[i].b);
        if(x==y) 
        {
            cout<<e[i].c;
            return 0;
        }
        //因为只有个2监狱，那么对一个人只有友族与敌族 
        f[y] = find(e[i].a + n);//b朋友的宗族==a敌人的宗族； 
        f[x] = find(e[i].b + n);//敌人的敌人就是朋友 
    }
    cout<<0;//完全无冲突 
    return 0;
}

并查集
#include<bits/stdc++.h>
using namespace std;
int n,m,f[40001],x,y;
struct data{
int a,b,c;
}e[100009];
int gz(const data &a,const data &b){
if(a.c>b.c)return 1;
else return 0;
}
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
int main(){
freopen("prison.in","r",stdin);
freopen("prison.out","w",stdout);
cin>>n>>m;
for(int i=1; i<=m; i++)
cin>>e[i].a>>e[i].b>>e[i].c;
for(int i=1; i<=n*2; i++)
f[i]=i;
sort(e+1,e+m+1,gz);
for(int i=1; i<=m; i++){
x=find(e[i].a);
y=find(e[i].b);
if(x==y){
cout<<e[i].c;
return 0;
}
f[y] = find(e[i].a + n);
f[x] = find(e[i].b + n);
}
puts("0");
return 0;
}

要使市长看到的事件影响最小，首先就可以想到贪心一下，把每两个人的冲突从大到小排个序。要尽量把冲突大的人分到不同监狱，但是怎么分不确定，我们就可以建立补集，采用两个并查集，把冲突大的两个人与彼此的补集相连。如果说当前有冲突的两个犯人已经被连在一起了，那么就停止。因为他们相连，就意味着他们有一位共同的敌人，通过这个敌人的补集他们连在了一起，而他们与这个敌人的冲突比他们之间的冲突要严重，所以他们两个在一个监狱最优。而我们是从大到小排序的，所以说先找到的就是这个监狱里冲突最大的。

#include<cstdio>
#include<algorithm>
using namespace std;
int f[40004];
struct held{
    int a,b,y;
}cri[100001];
int cmp(held p,held q)
{
    return p.y>q.y;
}
int fa(int x)                               //寻找祖先判断是否相连并沿途更新父节点。 
{                                           //并查集基本操作。 
    if (f[x]!=x) f[x]=fa(f[x]);
    return f[x];
}
int main()
{
    int n,m,i,g,h;
    bool ff=1;
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++) scanf("%d%d%d",&cri[i].a,&cri[i].b,&cri[i].y);
    for (i=1;i<=2*n;i++) f[i]=i;                       //初始化，自己是自己的父亲。 
    sort(cri+1,cri+1+m,cmp);
    for (i=1;i<=m;i++)
    {
        g=fa(cri[i].a); h=fa(cri[i].b);
        if (g==h) {printf("%d",cri[i].y); ff=0; break;}    //是否已经相连。 
        f[h]=fa(cri[i].a+n);                               //与彼此的补集相连。 
        f[g]=fa(cri[i].b+n);
    }
    if (ff) putchar('0');                                   //没有一点矛盾。 
    return 0;
}

类似最小生成树找到最大生成树，然后dfs进行染色，也就是把这棵树上相邻的点放进不同的监狱，之后考虑不在树上的边，如果边的两端点的颜色不同，不用考虑，如果相同，更新答案
//#include "stdafx.h"
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
#define maxn (int)1e7+10
#define INF 99999999
#define LDB long double
#define LL long long
using namespace std;
int v[400000], ne[400000], num[400000], len[400000], col[400000],head[400000],pre[400000],s[400000],t[400000],flag[400000];
int cot;
int addedge(int s, int t){
v[cot] = t; ne[cot] = head[s]; head[s] = cot++;
return 0;
}
int cmp(int a, int b) {
return len[a] > len[b];
}
int dfs(int s) {
for (int i = head[s]; i != -1; i = ne[i]) {
if (col[v[i]] != -1)
continue;
col[v[i]] = 1 - col[s];
dfs(v[i]);
}
return 1;
}
int findf(int x) {
int p = x;
while (pre[x] != x)
x = pre[x];
int c;
while (p != x) {
c = pre[p];
pre[p] = x;
p = c;
}
return x;
}
int add(int a, int b) {
int f1 = findf(a); int f2 = findf(b);
if (f1 != f2) {
pre[f2] = f1;
}
return 0;
}
int main() {
int n, m;
while (scanf("%d%d", &n, &m)!= EOF) {
cot = 0;
memset(head, -1, sizeof(head));
memset(flag, 0, sizeof(flag));
memset(col, -1, sizeof(col));
for (int i = 0; i <= n; i++)
pre[i] = i;
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &s[i], &t[i], &len[i]);
num[i] = i;
}
sort(num, num + m, cmp);
for (int i = 0; i < m; i++) {
int j = num[i];
if (findf(s[j]) != findf(t[j])) {
addedge(s[j], t[j]);
addedge(t[j], s[j]);
flag[num[i]] = 1;
add(s[j], t[j]);
}
}
dfs(1);
int ans = 0;
for (int i = 0; i < m; i++) {
if (flag[i])
continue;
if (col[s[i]] == col[t[i]])
ans = max(ans, len[i]);
}
printf("%d\n", ans);
}
}

之前用二分图染色那种方法做着试了试 得了90 一个点超时 应该是我写的那个太丑了 有人用二分图过了
下面用的是并查集 但我理解了半天才明白

并查集用来维护元素在同一个集合比较好用 比较好理解 即他们的根相等 他们就在同一个集合
现在要维护的是不在同一个集合 不好弄
如果我们用f[i]=j表示i与j不在同一个监狱
那么就会出现这种错误
比如a与b不在一个监狱 b与c不在一个监狱
那a与c呢 若按照上述方法 那么此时a与c的祖先一定相等 也就是代表a与c不在一个监狱 而事实上a与c是在同一个监狱里的

所以我们设了一些虚的点
比如现在我们要合并i j
那么
f[find(i)]=find(j+n)
f[find(j)]=find(i+n)
表示i与j不在同一个监狱
这样i与j的祖先是不同的 避免了上述错误

分析这个例子
4 6
1 2 9
3 4 7
1 3 6
2 3 3
1 4 2
2 4 1
按边权排好序后开始合并
1 2 9
f[1]=2+n
f[4]=3+n
3 4 7
f[3]=4+n
f[4]=3+n
1 3 6
f[find(1)]=find(3+n)---->f[2+n]=3+n
f[find(3)]=find(1+n)---->f[4+n]=1+n
2 3 3
f[find(2)]=find(3+n)---->f[1+n]=3+n
f[find(3)]=find(2+n)---->f[1+n]=3+n
此时f[find(2)]=f[find(3)]就出现了矛盾
两个人分别和他们的祖先不在同一个监狱里 而他们的祖先是一个人 就注定他们两个人必须在同一个监狱
此时的就得出了答案

还有人的做法是另开了一个数组 本质上都是相同的

var
a,b,c:array[0..100009] of longint;
f:array[0..40009] of longint;
x,y,ans,i,n,m:longint;
procedure qsort(l,r:longint);
var i,j,bi,ti:longint;
begin
i:=l; j:=r;
bi:=c[(l+r) div 2];
repeat
while c[i]>bi do inc(i);
while c[j]<bi do dec(j);
if i<=j then
begin
ti:=a[i]; a[i]:=a[j]; a[j]:=ti;
ti:=b[i]; b[i]:=b[j]; b[j]:=ti;
ti:=c[i]; c[i]:=c[j]; c[j]:=ti;
inc(i); dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
function find(x:longint):longint;
begin
if f[x]=x then exit(x);
f[x]:=find(f[x]);
exit(f[x]);
end;
begin
readln(n,m);
for i:=1 to m do read(a[i],b[i],c[i]);
qsort(1,m);
//writeln; for i:=1 to m do writeln(a[i],' ',b[i],' ',c[i]);
for i:=1 to 2*n do f[i]:=i;
for i:=1 to m do
begin
x:=find(a[i]);
y:=find(b[i]);
if x=y then
begin
ans:=c[i];
break;
end else
begin
f[x]:=find(b[i]+n);
f[y]:=find(a[i]+n);
end;
end;
writeln(ans);
end.

type
node=record
head,tail,data:longint;
end;
var
n,m,i,fx,fy:longint;
link:array[1..100000]of node;
father,enemy:array[1..20000]of longint;
procedure qsort(l,r:longint);
var
i,j,mid:longint;
t:node;
begin
i:=l;
j:=r;
mid:=link[(l+r) div 2].data;
repeat
while link[i].data>mid do inc(i);
while link[j].data<mid do dec(j);
if i<=j then
begin
t:=link[i];link[i]:=link[j];link[j]:=t;
inc(i);dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
function getfather(u:longint):longint;
begin
if father[u]=u then exit(u)
else father[u]:=getfather(father[u]);
exit(father[u]);
end;
procedure union(u,v:longint);
var
fx,fy:longint;
begin
fx:=getfather(u);
fy:=getfather(v);
father[fx]:=fy;
end;
procedure init;
var
i:longint;
begin
readln(n,m);
for i:=1 to m do read(link[i].head,link[i].tail,link[i].data);
qsort(1,m);
for i:=1 to n do father[i]:=i;
fillchar(enemy,sizeof(enemy),0);
end;
procedure work;
var
i,j,fx,fy:longint;
begin
for i:=1 to m do
begin
fx:=getfather(father[link[i].head]);
fy:=getfather(father[link[i].tail]);
if fx=fy then
begin
write(link[i].data);
halt;
end;
if enemy[link[i].head]=0 then enemy[link[i].head]:=link[i].tail;
if enemy[link[i].tail]=0 then enemy[link[i].tail]:=link[i].head;
union(enemy[link[i].head],link[i].tail);
union(enemy[link[i].tail],link[i].head);
end;
end;
begin
init;
work;
write('0');
end.

#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;

struct Enemynode
{
int first,second,cost;
bool operator < (const Enemynode b)const
{
return cost>b.cost;
}
}Enemy[100001];

int N,M,father[40001];

int get_father(int x)
{
if (x==father[x]) return x;
return father[x]=get_father(father[x]);
}

int main()
{
cin>>N>>M;
for(int i=1;i<=(N<<1);i++)
father[i]=i;
for(int i=0;i<M;i++)
cin>>Enemy[i].first>>Enemy[i].second>>Enemy[i].cost;
sort(Enemy,Enemy+M);
for(int i=0;i<M;i++)
{
int x=get_father(Enemy[i].first),y=get_father(Enemy[i].second);
if (x==y)
{
cout<<Enemy[i].cost;
return 0;
}
father[x]=get_father(Enemy[i].second+N);
father[y]=get_father(Enemy[i].first+N);
}
cout<<0;
return 0;
}

var n,m,i,j,x,y:longint;a,b,c,f:array[0..100000] of longint;
procedure xc(var x,y:longint);
var t:longint;
begin
t:=x;x:=y;y:=t;
end;
procedure qsort(l,r:longint);
var x,y,mid:longint;
begin
x:=l; y:=r; mid:=c[(x+y) div 2];
repeat
while c[x]>mid do inc(x);
while c[y]<mid do dec(y);
if x<=y then
begin
xc(a[x],a[y]);
xc(b[x],b[y]);
xc(c[x],c[y]);
inc(x); dec(y);
end;
until x>y;
if x<r then qsort(x,r);
if l<y then qsort(l,y);
end;

procedure shut(i:integer);
begin
writeln(c[i]);
halt;
end;

function getf(x:longint):longint;
begin
if f[x]=x then exit(x);
exit(getf(f[x]));
end;
begin
readln(n,m);
for i:=1 to m do
readln(a[i],b[i],c[i]);
qsort(1,m);
for i:=1 to n do f[i]:=i;
for i:=1 to m do
begin
x:=getf(a[i]);
y:=getf(b[i]);
if x=y then shut(i);
f[x]:=y;
end;
writeln(0);
end.

贪心+并查集

#include <cstdio>
#include <algorithm>
using namespace std;
int f[20004],g[20004];
int n,m;
struct Edge
{
int c,u,v;
inline void Read()
{
scanf("%d%d%d",&u,&v,&c);
}
}C[100005];
int getf(int x)
{
if (x==f[x]) return x;
int fa=getf(f[x]);
g[x]^=g[f[x]];
return f[x]=fa;
}
inline bool cmp(const Edge& A,const Edge& B)
{
return A.c>B.c;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
C[i].Read();
for (int i=1;i<=n;i++)
f[i]=i;
sort(C+1,C+m+1,cmp);
for (int i=1;i<=m;i++)
{
int u=getf(C[i].u),v=getf(C[i].v);
if (u==v)
{
if (g[C[i].u]==g[C[i].v])
{
printf("%d\n",C[i].c);
return 0;
}
continue;
}
g[v]=g[C[i].u]^g[C[i].v]^1;
f[f[v]]=u;
}
puts("0");
return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 1768 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1768 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1772 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1776 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1776 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 1772 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 1772 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 1776 KiB, score = 10
测试数据 #8: Accepted, time = 62 ms, mem = 1772 KiB, score = 10
测试数据 #9: Accepted, time = 62 ms, mem = 1768 KiB, score = 10
Accepted, time = 216 ms, mem = 1776 KiB, score = 100

我的思路是基于一个基本结论的（在这道题）
由于只有两个监狱，所以
若a和b不在同一监狱
若b和c不在同一监狱
则a和c在同一监狱。
而我的原则是，尽量把两个怨气值大的两个人关到不同的监狱中去
所以首先就快排（按怨气值从大到小）
然后就开始处理怨气了（当然是从最大的开始）——
1. 如果这个两个人已经在同一监狱中了，ok，不用干了，他们的怨气值就是最大（什么，你要把他们分开，那会导致更大的怨气）
a. 把这两个人关到不同的监狱（怎么关?）
b. a和b的监狱不同，把a的祖先改为（b+n）的祖先。同理b的祖先改为……
c. 为什么这样干？因为倘若再有一个人c和b合不来，然后c的祖先同样的也要置为b+n的祖先。如此以来a和c的父亲也就相同。而父亲相同就代表他们在同一监狱。于是……

比较混乱，看看代码吧

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

typedef struct {
int a,b,cost;
}node;

node person[100002];
int f[40002];
int n,m;

void init()
{
int i;
scanf("%d%d",&n,&m);
for (i = 1;i <= m;i++)
scanf("%d%d%d",&person[i].a,&person[i].b,&person[i].cost);
}

int tmp;
void swap(node *a,node *b)
{
tmp = a->a; a->a = b->a; b->a = tmp;
tmp = a->b; a->b = b->b; b->b = tmp;
tmp = a->cost; a->cost = b->cost; b->cost = tmp;
}

node mid;
void quicksort(node *front,node *rear)
{
node *i,*j;
i = rand()%(rear-front+1)+front;
mid.a = i->a; mid.b = i->b; mid.cost = i->cost;
swap(rear,i);
i = front; j = rear;
while (i <= j){
while (i->cost > mid.cost) i++;
while (j->cost < mid.cost) j--;
if (i <= j) {
swap(i,j);
i++,j--;
}
}
if (i < rear) quicksort(i,rear);
if (j > front) quicksort(front,j);
}

long find(int a)
{
if (a == f[a])
return a;
else
return f[a] = find(f[a]);
}

int main()
{
int i,sa,sb,ans;
/*freopen("zui.in","r",stdin);
freopen("zui.out","w",stdout);*/
for (i = 0;i < 100002;i++)
person[i].cost = 0;
init();
srand(time(NULL));
quicksort(&person[1],&person[m]); /*按怨气值排序从大到小*/
for (i = 1;i <= 2*n;i++)
f[i] = i; /*每个人的“父”为自己*/
ans = -1;
for (i = 1;i <= m;i++) {
sa = find(person[i].a); /*甲方父*/
sb = find(person[i].b); /*乙方父*/
if (sa == sb) {/*父相同
即两人已经在同一个监狱中），题目所求的就是两个人的怨气值*/
ans = i;
break;
} else {
f[sa] = f[find(person[i].b+n)];
f[sb] = f[find(person[i].a+n)];/*甲乙关到不同的监狱中*/
}
}
if (ans == -1)
printf("0");
else
printf("%d",person[ans].cost);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}

二分答案，将边权大于二分值的边加入图中，然后判断是否为二分图。
测试数据 #0: Accepted, time = 0 ms, mem = 4652 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 4652 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 4656 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 4656 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 4656 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 4656 KiB, score = 10
测试数据 #6: Accepted, time = 62 ms, mem = 4656 KiB, score = 10
测试数据 #7: Accepted, time = 62 ms, mem = 4656 KiB, score = 10
测试数据 #8: Accepted, time = 140 ms, mem = 4656 KiB, score = 10
测试数据 #9: Accepted, time = 171 ms, mem = 4652 KiB, score = 10
Accepted, time = 480 ms, mem = 4656 KiB, score = 100

乱七八糟的方法，以为可以暴力的，结果wa#include<stdio.h>
int main()
{
int n,m; //罪犯人数，有矛盾的对数.
int i,j;
long a[20000];long b[20000];long c[20000]; //罪犯编号，怨气值.
long d[20000];long e[20000];long f[20000]; //进入甲乙监狱的人，相应怒气值.
int answer;
scanf("%l",&n);
scanf("%l",&m);
for ( j=0 ; j<m ; j++)
{
scanf("%l",&a[j]);
scanf("%l",&b[j]);
scanf("%l",&c[j]);
}
for (i=0 ; i<j ; i++)
{
if ( c[j] > c[j+1] )
{
d[i]=c[j];
e[i]=a[j];
f[i]=b[j];
}
for ( i=0 ; i<j ; i++)
{
if (f[i]>f[i+1])
answer=f[i+1];
}
}
printf("%l",answer);
return 0;
}

#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;

}

测试数据 #0: Accepted, time = 0 ms, mem = 1872 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1868 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1868 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1872 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1864 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1864 KiB, score = 10
测试数据 #6: Accepted, time = 46 ms, mem = 1868 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 1864 KiB, score = 10
测试数据 #8: Accepted, time = 62 ms, mem = 1864 KiB, score = 10
测试数据 #9: Accepted, time = 93 ms, mem = 1868 KiB, score = 10
Accepted, time = 232 ms, mem = 1872 KiB, score = 100

91ms，似乎是目前为止最快的代码
如果想要更快可以加点代码，可以50ms左右

思路来自此博客

关键思路：
既然本题是两个集合（显然使用并查集），那么如果a和b不在一个集合，b和c不在一个集合，a必须和c在一个集合
那么本题就是尽可能让大边的两个罪犯不要满足上述情况（先把所有边从大到小排一遍），一旦出现上述情况必须在一个集合内，那么即为解（因为排序过，所以必定比剩下的边都大）

所以

这个大佬的思路是用f[i] 记录与 i 同监狱的人，f[i+n]记录与 i 不同监狱的人。（即对立集合元素）

#include<bits/stdc++.h>
using namespace std;
const int maxn =20000;
const int maxm =100000;

using namespace std;  

int n,m,f[maxn*2+20];  

inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}

struct tnode{int a,b,c;}q[maxm+20]; 

bool cmp(tnode x,tnode y)  {return x.c>y.c;}  

int find(int x)  {return f[x]=(f[x]==x)?x:find(f[x]);}  
int main()  
{  
  int i,j,k,r1,r2,r3,r4;  
  n=read();m=read();
  for(i=1;i<=n;i++)f[i]=i,f[i+n]=i+n;  
  for(i=1;i<=m;i++) q[i].a=read(),q[i].b=read(),q[i].c=read();  
  sort(q+1,q+m+1,cmp);  
  for(i=1;i<=m;i++)  
    {  
      r1=find(q[i].a),r2=find(q[i].a+n);  
      r3=find(q[i].b),r4=find(q[i].b+n);  
      if(r1==r3 || r2==r4)break;  
      f[r3]=r2,f[r4]=r1;  
    }  
  if(i>m)printf("0\n");  
  else printf("%d\n",q[i].c);    
  return 0;  
}  

并查集+拆点
#include <algorithm>
#include <bitset>
#include <cctype>
#include <complex>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <vector>

using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define irep(i,a,b) for(int i=(a);i>(b);i--)
#define reset(a,c) memset(a,c,sizeof(a))

typedef long long int64;

const int inf = 0x3f3f3f3f;

const int maxN = 20000 + 5;
const int maxM = 100000 + 5;

struct Edge
{
int v1, v2, w;
bool operator < (const Edge& x) const
{
return w > x.w;
}
void read()
{
scanf ("%d%d%d", &v1, &v2, &w);
}
};

Edge edge[maxM];
int ufs[maxN << 1];
int N, M;

void input()
{
scanf ("%d%d", &N, &M);
rep (i, 0, M) edge[i].read();
}

int find (int x)
{
return ufs[x] == x ? x : ufs[x] = find (ufs[x]);
}

void link (int x, int y)
{
ufs[find (x)] = find (y);
}

int solve()
{
rep (i, 1, (N << 1) | 1) ufs[i] = i;
sort (edge, edge + M);
rep (i, 0, M)
{
int f1 = find (edge[i].v1);
int f2 = find (edge[i].v2);
if (f1 == f2) return edge[i].w;
link (edge[i].v1, edge[i].v2 + N);
link (edge[i].v2, edge[i].v1 + N);
}
return 0;
}

int main()
{
input();
printf ("%d\n", solve() );
return 0;
}

简单的二分加二分图染色
```c++
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

const int INF = 1000000000;
const int maxn = 20000 + 5;
const int maxm = 100000 + 5;
int n, m;
int L, R;
int color[maxn];
vector<int> G[maxn];

struct Edge {
int from, to, dist;
Edge (int a, int b, int c) : from(a), to(b), dist(c) {}
};

vector<Edge> edges;

void AddEdge (int u, int v, int w) {
G[u].push_back(edges.size());
edges.push_back(Edge(u, v, w));
G[v].push_back(edges.size());
edges.push_back(Edge(v, u, w));
}

int k;
bool bipartite (int u) {
for (int i = 0; i < G[u].size(); i++) {
Edge& e = edges[G[u][i]];
if (e.dist <= k) continue;
if (color[e.to] == color[u]) return false;
if (!color[e.to]) {
color[e.to] = 3 - color[u];
if (!bipartite(e.to)) return false;
}
}
return true;
}

bool check (int test) {
k = test;
for (int i = 0; i < n; i++) color[i] = 0;
for (int i = 0; i < n; i++)
if (!color[i]) {
color[i] = 1;
if (!bipartite(i)) return false;
}
return true;
}

int main ()
{
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w); u--; v--;
R = max(R, w);
AddEdge(u, v, w);
}

while (L < R) {
int M = L + (R - L) / 2;
if (check(M)) R = M; else L = M + 1;
}
cout << L;
return 0;
}
```

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
struct thief{
int one,two,anger;
};
struct thief a[100001];
int n,m,father[40005];
int comp(const struct thief&x,const struct thief&y)
{
return x.anger>y.anger;
}
void init()
{
int i;
scanf("%d%d",&n,&m);;
for(i=1;i<=m;i++){
scanf("%d%d%d",&a[i].one,&a[i].two,&a[i].anger);
}
for(i=1;i<=2*n;i++){
father[i]=i;
}
sort(a+1,a+m+1,comp);
}
int find(int t)
{
if(father[t]!=t){
father[t]=find(father[t]);
return father[t];
}
else{
return t;
}
}
void work()
{
int i;
for(i=1;i<=m;i++){
int temp1=find(a[i].one);
int temp2=find(a[i].two);
if(temp1!=temp2){
int temp3=find(a[i].one+n);
if(temp3!=temp2){
father[temp3]=temp2;
}
int temp4=find(a[i].two+n);
if(temp1!=temp4){
father[temp1]=temp4;
}
}
else{
printf("%d",a[i].anger);
return;
}
}
printf("0");
}
int main()
{
init();
work();
return 0;
}

二分图染色和二分答案即可
第一次写二分图染色，诸多细节都没有考虑到
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>

using namespace std;

struct P {
int x, y, len;
} p[100005];
struct Node {
int nextNode;
Node *next;
} *node[20005], pool[300005];

int n, m, cnt;
bool flag[100005];
bool f[20005];
int color[20005];
bool f2[20005];

bool dfs(int u) {
f2[u] = true;
for (Node *c = node[u]; c; c = c->next) {
int v = c->nextNode;
if (color[u] == color[v]) {
return false;
}
if (!color[v]) {
color[v] = 3 - color[u];
if (!dfs(v))
return false;
}
}
return true;
}
bool check(int mid) {
if (mid == m)
return true;
memset(color, 0, sizeof (color));
memset(node, 0, sizeof (node));
memset(pool, 0, sizeof (pool));
memset(f2, 0, sizeof (f2));
memset(f, 0, sizeof (f));
cnt = 0;
for (int i = mid + 1; i <= m; ++i) {
Node *c = &pool[++cnt];
c->nextNode = p[i].y;
c->next = node[p[i].x];
node[p[i].x] = c;
c = &pool[++cnt];
c->nextNode = p[i].x;
c->next = node[p[i].y];
node[p[i].y] = c;
f[p[i].x] = f[p[i].y] = true;
}
for (int i = 1; i <= n; ++i) {
if (!f[i])
continue;
if (!f2[i]) {
color[i] = 1;
if (!dfs(i)) {
return false;
}
}
}
return true;
}
bool cmp(P a, P b) {
return (a.len < b.len);
}
int main(int argc, const char *argv[]) {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i)
scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].len);
sort(p + 1, p + m + 1, cmp);
int ans = 0;
if (check(0)) {
printf("0\n");
return 0;
}
int l = 1, r = m;
while (l <= r) {
int mid = (l + r) / 2;
if (flag[mid])
break;
flag[mid] = true;
if (check(mid)) {
ans = mid;
r = mid;
}
else {
l = mid + 1;
}
}
printf("%d\n", p[ans].len);
return 0;
}

题解：http://www.cnblogs.com/xtx1999/p/4826922.html

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

int n , m;

struct edge
{
int x , y;
int v;
};

edge e[100000 + 2];

int cmp( edge a , edge b )
{
if( a.v > b.v )
return 1;
return 0;
}

int i;
int pre[400000 + 10];

int find( int x )
{
if( x == pre[x] )
return x;
return pre[x] = find( pre[x] );
}

void merge( int a , int b )
{
pre[ find( a ) ] = find( b );
return;
}

int main()
{
scanf( "%d %d" , &n , &m );
for( i = 1 ; i <= m ; i++ )
scanf( "%d %d %d" , &e[i].x , &e[i].y , &e[i].v );
for( i = 1 ; i <= n * 2 ; i++ )
pre[i] = i;
sort( e + 1 , e + m + 1 , cmp );
for( i = 1 ; i <= m ; i++ )
{
if( find( e[i].x ) != find( e[i].y ) )
{
merge( e[i].x , e[i].y + n );
merge( e[i].x + n , e[i].y );
}
else
{
cout << e[i].v << endl;
return 0;
}
}
cout << 0 << endl;
return 0;
}