题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2e4+10,M=2e5+10;
int h[N],e[M],ne[M],w[M],idx;
int color[N];
int n,m,a,b,c;
void add(int a,int b,int c)
{
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
bool dfs(int u,int c,int mid)
{
color[u]=c;
for(int i=h[u];i!=-1;i=ne[i])
{
if(w[i]<=mid) continue;
int j=e[i];
if(!color[j])
{
if(!dfs(j,3-c,mid)) return false;
}
if(color[j]==c) return false;
}
return true;
}
bool check(int mid)
{
memset(color,0,sizeof color);
for(int i=1;i<=n;i++)
if(!color[i])
if(!dfs(i,1,mid)) return false;
return true;
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c),add(b,a,c);
}
int l=0,r=1e9;
while(l<r)
{
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",l);
return 0;
}
blablabla
```