题目大意
有些罪犯,个别罪犯之间有怨恨值,现要把这些罪犯分配到两所监狱。要求同一所监狱内部的最大的罪犯间怨恨值最小。
解题思路
扩展域并查集
拆点,把一个罪犯分成本体和影子就是两个域。两个本体或两个影子在一个集合就能推出这两个罪犯在一所监狱。题目要求最大值最小,那么一个显然的贪心:按怨恨值从大到小将关系排序,尽量让怨恨值大的两个罪犯身处异地。到第一个矛盾点就已经找到答案。
二分答案+二分图染色
将罪犯视为点,怨恨值视为边权,关系是无向边。原问题变为了:将所有点分成两组,要使得各组内边权最大值尽可能小。那么二分$limit$,判断能否将所有点分成两组,使得所有权值大于$limit$的边都在组间,而不在组内。也就是判断由所有点以及所有权值大于$limit$的边构成的新图是否是二分图,染色法判断即可。
具体代码
扩展域并查集
#include <bits/stdc++.h>
using namespace std;
const int N = 20010, M = 1e5 + 10;
int n, m;
int p[N << 1];
struct Relation
{
int a, b, c;
bool operator<(const Relation &it) const
{
return c > it.c;
}
} q[M];
int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < N << 1; i++)
p[i] = i;
for (int i = 0; i < m; i++)
cin >> q[i].a >> q[i].b >> q[i].c;
sort(q, q + m); //按怨恨值从大到小将关系排序
int res = 0;
for (int i = 0; i < m; i++) //尽量让怨恨值大的两位分处不同监狱
{
if (find(q[i].a) == find(q[i].b))
{
res = q[i].c;
break;
}
p[find(q[i].a)] = find(q[i].b + N);
p[find(q[i].a + N)] = find(q[i].b);
}
cout << res << '\n';
return 0;
}
二分答案+二分图染色
#include <bits/stdc++.h>
using namespace std;
const int N = 20010, M = 2e5 + 10;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
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 u, int c, int limit)
{
color[u] = c;
for (int i = h[u]; ~i; 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] == 0)
{
if (!dfs(i, 1, limit))
return false;
}
}
return true;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> 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 << '\n';
return 0;
}