```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef struct bian{
long a,b,w;
}biu;
biu list[200086];
long n,m,i,j,ok=0,f[20086]={0},q[20086]={0},c[20086]={0};
long long hd=0,ld=1000000000,k=0;
bool bfs(){
memset(q,0,sizeof(q));
memset(c,0,sizeof(c));
for(i=1;i<=n;i++)
{
if(!c[i])
{
q[++q[0]]=i,c[i]=1;
int z=q[0];
while(z<=q[0])
{
for(j=f[q[z]];j<f[q[z]+1] && j<2*m;j++)
{
if(list[j].w<k) continue;
if(c[list[j].b]==c[q[z]]) return false;
else if(!c[list[j].b]) q[++q[0]]=list[j].b,c[list[j].b]=-c[q[z]];
}
z++;
}
}
}
return true;
}
void isort(long a,long b){
long bl,el,z;
bl=a,el=b; z=bl;
while(bl<el)
{
while(bl<el)
{
if(list[z].a>list[el].a) {swap(list[z].a,list[el].a); swap(list[z].b,list[el].b); swap(list[z].w,list[el].w); z=el; break;}
el--;
}
while(bl<el)
{
if(list[z].a<list[bl].a) {swap(list[z].a,list[bl].a); swap(list[z].b,list[bl].b); swap(list[z].w,list[bl].w); z=bl; break;}
bl++;
}
}
if(bl-1>a)
isort(a,bl-1);
if(el+1<b)
isort(el+1,b);
}
int main() {
scanf("%ld %ld",&n,&m);
for(i=1;i<=m;i++)
{
long a,b,c;
scanf("%ld %ld %ld",&a,&b,&c);
list[2*i-2].a=a,list[2*i-2].b=b,list[2*i-2].w=c;
list[2*i-1].b=a,list[2*i-1].a=b,list[2*i-1].w=c;
}
long w=m*2;
isort(0,w-1);
for(i=0;i<2*m;i++) if(!f[list[i].a] && list[i].a!=1) f[list[i].a]=i;
if(bfs()) ok=1;
else while(hd<ld-1)
{
k=(hd+ld)/2;
if(bfs()) ld=k;
else hd=k;
}
k=ld;
if(ok) printf("0");
else if(bfs()) printf("%lld",hd);
else printf("%lld",ld);
return 0;
}
```
by kkxhh @ 2018-05-12 20:06:39
重新改了一下只剩下第三个点过不了了
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef struct bian{
long a,b,w;
}biu;
biu list[200086];
long n,m,i,j,ok=0,f[20086]={0},q[20086]={0},c[20086]={0};
long hd=0,ld=0,k=0;
bool bfs(){
memset(q,0,sizeof(q));
memset(c,0,sizeof(c));
for(i=1;i<=n;i++)
{
if(!c[i])
{
q[++q[0]]=i,c[i]=1;
int z=q[0];
while(z<=q[0])
{
if(f[q[z]]!=-1)
for(j=f[q[z]];j<f[q[z]+1] && j<2*m;j++)
{
if(list[j].w<k) continue;
if(c[list[j].b]==c[q[z]]) return false;
else if(!c[list[j].b]) q[++q[0]]=list[j].b,c[list[j].b]=-c[q[z]];
}
z++;
}
}
}
return true;
}
void isort(long a,long b){
long bl,el,z;
bl=a,el=b; z=bl;
while(bl<el)
{
while(bl<el)
{
if(list[z].a>list[el].a) {swap(list[z].a,list[el].a); swap(list[z].b,list[el].b); swap(list[z].w,list[el].w); z=el; break;}
el--;
}
while(bl<el)
{
if(list[z].a<list[bl].a) {swap(list[z].a,list[bl].a); swap(list[z].b,list[bl].b); swap(list[z].w,list[bl].w); z=bl; break;}
bl++;
}
}
if(bl-1>a)
isort(a,bl-1);
if(el+1<b)
isort(el+1,b);
}
int main() {
// freopen("testdata.in","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%ld %ld",&n,&m);
for(i=1;i<=m;i++)
{
long a,b,c;
scanf("%ld %ld %ld",&a,&b,&c);
ld=max(ld,c);
list[2*i-2].a=a,list[2*i-2].b=b,list[2*i-2].w=c;
list[2*i-1].b=a,list[2*i-1].a=b,list[2*i-1].w=c;
}
ld++;
isort(0,m*2-1);
memset(f,-1,sizeof(f));
for(i=0;i<2*m;i++) if(f[list[i].a]==-1) f[list[i].a]=i;
while(hd<ld-1)
{
k=(hd+ld)/2;
if(bfs()) ld=k;
else hd=k;
}
k=ld;
if(bfs()) printf("%ld",hd);
else printf("%ld",ld);
return 0;
}
```
------------
by kkxhh @ 2018-05-12 21:34:41