思路是二分答案。
两个极端情况:
1 如果没有人互相仇恨,那答案是0。
2 如果把所有人都放在一起,那答案就是最高仇恨值。
所以最后答案一定是某一个仇恨值。
我们猜一个仇恨值,然后验证只走比这个仇恨值高的边,能不能形成二分图。
如果可以,那说明猜大了,可能还有更小的仇恨值也能二分图。
如果不行,那说明猜小了,不能二分图,我们去猜一个更大的仇恨。
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 1e9+7;
typedef pair<int, int> PII;
const int N = 20010;
const int M = 200010;
int adjList[N], e[M], ne[M], w[M], idx;
int st[N];
int n, m;
vector<int> vec;
void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = adjList[a];
adjList[a] = idx++;
}
bool dfs(int u, int p, int color, int c) {
if (st[u] == color)
return false;
if (st[u] && st[u] != color)
return true;
st[u] = color;
for (int i = adjList[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == p || w[i] <= c)
continue;
if (dfs(v, u, -color, c))
return true;
}
return false;
}
bool verify(int c) {
// cout << "chcking" << c << endl;
memset(st, 0, sizeof st);
for (int i = 1; i <= n; i++) {
if (st[i])
continue;
if (dfs(i, -1, 1, c))
return false;
}
return true;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
memset(adjList, -1, sizeof adjList);
scanf("%d%d", &n, &m);
while (m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
vec.push_back(c);
}
vec.push_back(0);
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
int start = 0, end = vec.size() - 1;
while (start + 1 < end) {
int mid = start + end >> 1;
if (verify(vec[mid]))
end = mid;
else
start = mid;
}
if (verify(vec[start]))
cout << vec[start];
else
cout << vec[end];
return 0;
}
这题还有一个并查集的做法,先欠下。