裸搜bfs

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#define N 1000000
using namespace std;
int q[N],a[N],b[N],w[N],p[N],nextaa[N],n,m,maxv=-1,mid,le,ri,flag,color[N];
void inti()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=2*m;i+=2)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
maxv=max(maxv,z);
a[i]=x,b[i]=y,w[i]=z,nextaa[i]=p[x],p[x]=i;
a[i+1]=y,b[i+1]=x,w[i+1]=z,nextaa[i+1]=p[y],p[y]=i+1;
}
}
/*void dfs(int x)
{
int e=p[x];
while(e>0)
{
int k=b[e];
if(w[e]>=mid)
{
if(color[k]==0)
{
color[k]=3-color[x];
dfs(k);
}
else
if(color[k]==color[x])
{
flag=1;return;
}
}
e=nextaa[e];
}
}*/
void bfs(int x)
{
int fr=1,ta=0;
q[1]=x;
while(ta<fr)
{
int k=q[++ta];
int e=p[k];
while(e>0)
{
int kk=b[e];
if(w[e]>=mid)
if(!color[kk])
{
color[kk]=3-color[k];
q[++fr]=kk;
}
else
if(color[kk]==color[k])
{
flag=1;return;
}
e=nextaa[e];
}
}
}
int main()
{
inti();
ri=maxv;
while(le<=ri)
{
flag=0;
memset(color,0,sizeof(color));
mid=(ri+le)/2;
for(int i=1;i<=n;i++)
{if(color[i]==0)bfs(i);}
if(flag==1){le=mid+1;}
else{ri=mid-1;}
}
if(ri<0)cout<<0;
else cout<<ri;
return 0;
}

0 条评论

目前还没有评论...

信息

ID
1776
难度
6
分类
图结构 | 二分图 点击显示
标签
递交数
3543
已通过
1015
通过率
29%
被复制
11
上传者