P1955. 程序自动分析

发表于 分类于 阅读次数： Waline： 本文字数： 606 阅读时长 ≈ 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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e6 + 10;
int n, tot, fa[LEN], discre[LEN << 1];

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

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;
}

void init() {
  // 离散化开始
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> arr[i].x_ >> arr[i].y_ >> arr[i].e_;
    discre[tot++] = arr[i].x_, discre[tot++] = arr[i].y_;
  }
  sort(discre, discre + tot);
  tot = unique(discre, discre + tot) - discre;
  for (int i = 1; i <= n; ++i) {
    arr[i].x_ = lower_bound(discre, discre + tot, arr[i].x_) - discre + 1;
    arr[i].y_ = lower_bound(discre, discre + tot, arr[i].y_) - discre + 1;
  }
  // 离散化结束
  for (int i = 1; i <= tot; ++i) fa[i] = i;
}

void work() {
  init();
  sort(arr + 1, arr + 1 + n,
       [](node &a, node &b) -> bool { return a.e_ > b.e_; });
  for (int i = 1; i <= n; ++i) {
    if (arr[i].e_) {
      join(arr[i].x_, arr[i].y_);
    } else {
      if (find(arr[i].x_) == find(arr[i].y_)) {
        cout << "NO" << endl;
        return;
      }
    }
  }
  cout << "YES" << endl;
}

int main() {
  int t;
  cin >> t;
  while (t--) work();
  return 0;
}

思路

本题不能使用扩展域并查集或边带权并查集，从两个角度分析

边带权并查集

举个例子：

  • A和B相等，B和C相等，能推出A等于C

  • A和B相等，B和C不等，能推出A不等于C

  • A和B不等，B和C相等，能推出A不等于C

  • A和B不等，B和C不等，A和C能确定唯一的关系吗？不能吧

    假设A等于1，B等于2，C也等于1，此时A等于C

    若A等于1，B等于2，C等于3，此时A不等于C

    并查集是不能处理重边的，它本身只是一个森林

A(A与B的关系边权) B(B与C的关系边权) C(A与C的关系边权)
1 1 1
1 0 0
0 1 0
0 0 ?

扩展域并查集

举个例子：

1 2 0

2 3 0

也就是1不等于2, 2不等于3

按照扩展域的处理方式，原长度存储相等关系，扩大一倍的长度存储不等关系

那么有{1+n, 2}、{2+n, 1}、{2+n, 3}、{3+n, 2}

合并后的结果为{1+n, 3+n, 2}、{2+n, 1, 3}

可是1和3之间的关系并不能确定啊？你这就把它俩放一个集合了？

正解

首先离散化，1e9的数据范围肯定会炸

通过排序，先处理相等关系，然后再判断不等关系是否与相等关系矛盾即可