P1525. 关押罪犯

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 508 阅读时长 ≈ 2 分钟

考点

  • 扩展域并查集
  • 贪心
  • 二分图

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e5 + 10;
//扩大一倍
int n, m, fa[LEN << 1];

int find(int x) {
  if (fa[x] == x) return x;
  return fa[x] = find(fa[x]);
}

void join(int x, int y) {
  int a = find(x), b = find(y);
  fa[a] = b;
}

struct node {
  int x_, y_, w_;
} arr[LEN];

int main() {
  cin >> n >> m;
  //扩大的那一倍也要初始化
  for (int i = 1; i <= (n << 1); ++i) fa[i] = i;
  for (int i = 1; i <= m; ++i) {
    cin >> arr[i].x_ >> arr[i].y_ >> arr[i].w_;
  }
  sort(arr + 1, arr + 1 + m,
       [](node &a, node &b) -> bool { return a.w_ > b.w_; });
  int x, y, a, b;
  for (int i = 1; i <= m; ++i) {
    x = arr[i].x_, y = arr[i].y_;
    if ((a = find(x)) == (b = find(y))) {
      cout << arr[i].w_;
      return 0;
    }
    join(x, y + n), join(y, x + n);
  }
  cout << 0;
  return 0;
}

思路

扩展域并查集的模板题

很容易想到贪心策略，将仇恨值从大到小排，优先拆开仇恨值大的，即可保证后续数据组成的集合仇恨值尽量小

样例为例，排序后得到数据如下，自上而下处理：

x y w
1 2 28351
3 4 12884
1 3 6618
2 3 3512
1 4 2534
2 4 1805

对于每个人而言，都有两种关系：“我的朋友”和“我的敌人”

扩展域并查集中，多一种关系就扩大一倍空间以存储额外的关系；在这里，多出来的一倍空间存储我的敌人集合

假设当前有输入1 2 28351

2应该放在1 + n同一集合，意为将2放入1的敌人集合

相应的，1应该放在2 + n同一集合，意为将1放入2的敌人集合

重复上述操作，直到发现当前两个人已经在同一集合内，无法再拆；此时就得到了最大的仇恨值，输出即可

我们是以仇恨值从大到小的顺序拆开两个人的

若当前二人已在同一集合，是之前拆分更大仇恨值得到的结果

如果依旧再拆，岂不是违背贪心策略吗？