文章

25

粉丝

0

获赞

0

访问

244786

头像
二分图+二分
经验总结
发布于2020年4月16日 21:36
阅读数 8223

#include<iostream>
#include<cstring>
using namespace std;
const int N = 20010;
const int M = 200010;
int h[N], e[M], next_pos[M], w[M], idx;
int color[N];
int n, m;
void add(int a, int b, int c){
	e[++idx] = b;
	w[idx] = c;
	next_pos[idx] = h[a];
	h[a] = idx;
}
bool dfs(int u, int c, int limit){
	color[u] = c;
	for (int i = h[u]; i; i = next_pos[i]){
		int j = e[i];
		if (w[i] <= limit){ continue; }
		if (color[j] == 0){
			if (!dfs(j, 3-c, limit)){ return false; }
		}
		else if (color[j] == c){
			return false;
		}
	}
	return true;
}
bool check(int limit){
	memset(color, 0, sizeof color);
	for (int i = 1; i <= n; i++){
		if (color[i] == 0){
			if (!dfs(i, 1, limit)){
				return false;
			}
		}
	}
	return true;
}
int main(){
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int x, y, w;
		cin >> x >> y >> w;
		add(x, y, w);
		add(y, x, w);
	}

	int l = 0, r = 1e9;
	while (l < r){
		int mid = l + r >> 1;
		if (check(mid)){
			r = mid;
		}
		else{
			l = mid + 1;
		}

	}

	cout << l << endl;

	return 0;
}

 



登录后发布评论

暂无评论,来抢沙发