算法1
并查集(带权边)
个人偏爱
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 20010;
int p[M], d[M];
int n, m;
struct Prisons{
int a, b, w;
}ps[N];
bool cmp(Prisons a,Prisons b) {
return a.w > b.w;
}
int find(int x) {
if (x != p[x]) {
int t = find(p[x]);
d[x] ^= d[p[x]];
p[x] = t;
}
return p[x];
}
int main() {
cin >> n >> m;
for (int i = 1; i < M; i++) p[i] = i;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &ps[i].a, &ps[i].b, &ps[i].w);
}
//将所有怨气值由大到小排序
sort(ps + 1, ps + 1 + m, cmp);
for (int i = 1; i <= m; i++) {
int a = ps[i].a, b = ps[i].b;
int pa = find(a), pb = find(b);
//确定a,b在一组
if (p[a] == p[b]) {
if (d[a] ^ d[b] ^ 1) {//d[a]与d[b]奇偶性相同
cout << ps[i].w << endl;
return 0;
}
}
//否则将a归到不可能与b的一组(贪心)
else {
p[pa] = pb;
d[pa] = d[a] ^ d[b] ^ 1;//维护距离使a,b奇偶性不同
}
}
cout << 0 << endl;
return 0;
}
算法2
并查集(拓展域)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 20010;
int p[2 * M];
int n, m;
struct Prisons{
int a, b, w;
}ps[N];
bool cmp(Prisons a,Prisons b) {
return a.w > b.w;
}
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main() {
cin >> n >> m;
for (int i = 1; i < 2 * M; i++) p[i] = i;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &ps[i].a, &ps[i].b, &ps[i].w);
}
//将所有怨气值由大到小排序
sort(ps + 1, ps + 1 + m, cmp);
for (int i = 1; i <= m; i++) {
int pa = find(ps[i].a), pb = find(ps[i].b);
//确定a,b只能在一组
if (pa == pb) {
cout << ps[i].w << endl;
return 0;
}
//否则将a归到不可能与b(ps[i].b + M)的一组(贪心)
//这里可能会想不写find函数,例如b也不可能与c一组,则p[pc] = ps[i].b + M = p[pa],也说明a只能与c一组
//然而,当我们再次询问a时,pa已经等于ps[i].b + M了,如果没有find函数则无法再次将pa的值更新
// p[pa] = find(ps[i].b + M);
// p[pb] = find(ps[i].a + M);
//其实主要思想还是将a所在的整个集合与ps[i].b + M所在的整个集合相连,上下两种写法是一样的
p[find(ps[i].b + M)] = pa;
p[find(ps[i].a + M)] = pb;
}
cout << 0 << endl;
return 0;
}
算法3
二分图,二分答案
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20010, M = 2e5 + 10;
int h[N], e[M], ne[M], w[M], idx;
int color[N];
int n, m;
void add(int a, int b, int x) {
e[idx] = b, w[idx] = x, ne[idx] = h[a], h[a] = idx++;
}
bool dfs(int u, int c, int x) {
color[u] = c;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (w[i] <= x) continue;
if (!color[j]) {
if (!dfs(j, 3 - c, x))
return false;
}
else if (color[j] != 3 - c) 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;
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i++) {
int a, b, x;
scanf("%d%d%d", &a, &b, &x);
add(a, b, x), add(b, a, x);
}
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;
}