https://www.acwing.com/problem/content/description/259/
閆總的思路很好，把它放在一個二分圖當中，二分解決，也就是說，把大于limit的放到二分圖左右兩部分的中間，觀察是否能形成二分圖，如果可以形成，說明limit 是可以成立的，二分圖的證明方法是染色法時間復雜度是o(N）級別的，非常的不錯哈，然后對其進行二分，我覺得y總一說思路，再學一下基礎演算法，這道題還是很簡單的，然后代碼如下，
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e4+10,M=1e5+10;
int h[N],ne[2*M],e[2*M],w[2*M],idx;
int n,m;
int color[N];
void add(int a,int b,int c)
{
e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
bool dfs(int x,int c,int limit)
{
color[x]=c;
for(int i=h[x];i!=-1;i=ne[i])
{
if(w[i]<=limit)
continue;
int j=e[i];
if(color[j])
{
if(color[j]==c)
return false;
}
else if(!dfs(j,3-c,limit)) return false;
}
return true;
}
bool check(int limit)
{
memset(color,0,sizeof color);
for(int i=1;i<=n;i++)
{
if(!color[i])
{
if(!dfs(i,1,limit))
return false;
}
}
return true;
}
int main(void)
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
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;
}
cout<<l;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261806.html
標籤：其他
下一篇：第一次親密接觸IT技術（第一天）