淘客做自己的网站/微信推广广告在哪里做

前言

传送门 :

思路

回顾 :
二分图 : 能被分成两个集合,并且边在都在集合之间,单个集合之内没有相连的边

因为题目中有 最大的怒气值最小 的意味,我们考虑使用二分怒气值

我们考虑将 所有大于$mid$的边 放在集合中间, 也即是我们考虑将 这个图分成两半

如果 中间的边都大于$mid$ 而集合内的边都**小于$mid$**显然是一个解

因此我们不断使用二分即可找到答案

Mycode

const int N = 2e4+10 ;struct node{int to,val;
};vector<node> g[N];
int n,m;
int  color[N];bool dfs(int u,int c,int x){color[u] = c;for(auto j : g[u]){if(j.val <= x) continue;if(color[j.to]) {if(color[j.to] == c)return false;}else if(!dfs(j.to,3-c,x)) return false;}return true;
}bool check(int x){memset(color,0,sizeof color);for(int i=1;i<=n;i++)if(!color[i])if(!dfs(i,1,x)) return false;//染色失败return true;
}
void solve(){cin>>n>>m;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;g[a].pb({b,c});g[b].pb({a,c});}int l = 0 , r = 1e9;while(l<=r){int mid = (l+r)>>1;if(check(mid)) r = mid-1;else l = mid+1;}cout<<l<<endl;
}