HDU 4829 Information 带权并查集模拟

100 阅读 0 评论 66 点赞

我是靠谱客的博主无限小甜瓜，这篇文章主要介绍HDU 4829 Information 带权并查集模拟，现在分享给大家，希望可以做个参考。

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4829

题意

一道有6个操作的模拟题：
军情紧急，我们需要立刻开发出一个程序去处理前线侦察兵发回的情报，并做出相应的分析。现在由你负责其中的一个子模块，你需要根据情报计算出敌方坦克的位置。
当敌方坦克静止时，侦察兵会尽力估算出它们之间的位置，而每当敌方坦克移动时，侦察兵都会记录下坦克新的位置并向你报告。每个坦克的位置可以由一个二维整数坐标来描述。
前线发回的情报有四种格式：
1 A B X Y
表示A坦克移动到了与B坦克的相对位置是(X,Y)的地方，即XA = XB + X, YA=YB+Y。
2 A X Y
表示A坦克移动到了绝对位置是(X,Y)的地方，即XA = X, YA = Y。
3 A B X Y
表示发现了A坦克与B坦克的相对位置是(X,Y)，即XA = XB + X, YA=YB+Y。
4 A X Y
表示发现了A坦克的绝对位置是(X,Y)，即XA = X, YA = Y。
我们需要你对于如下两种询问及时做出回应：
5 A B
表示询问A坦克与B坦克的相对位置是多少，即分别求出XA - XB 以及YA -YB。
6 A
表示询问A坦克的绝对位置是多少，即求出XA 和YA。
其中A和B代表的是任意的一个坦克的编号，(X,Y)表示了坦克的二维坐标。你可以假设初始时刻我们对于敌方任何坦克的位置都一无所知，在此之后坦克的每一次移动都被侦察兵侦察到了。
请注意两个坦克的坐标有可能相同。

对于每组数据，首先需要输出单独一行”Case #?:”，其中问号处应填入当前的数据组数，组数从1开始计算。
对于每一个类型(1)或者(2)的询问，请把它们加入到你的记录中。
对于每一个类型(3)或者(4)的询问，如果与之前记录的内容有矛盾，请输出”REJECT”并将这个情报忽略掉，如没有矛盾，请把它们加入到你的记录中。
对于每一个类型(5)或者(6)的询问，如果根据之前的记录能推出结论，请输出两个整数X和Y，两个整数之间有一个空格；如果不能推出结论，请输出”UNKNOWN”。输出的所有信息都不包括引号。

思路：

用带权并查集进行纯模拟，好久没做这种题了，后来看了别人的题解才会，考虑到这篇题解我百度不到 = =（百度到的题解有问题），自己也写一写把。

首先模拟题最好是分析清楚题意，捋清各个操作之间的异同，这样代码写起来简短易读，不然一个又一个的if else让人看了头大= =

带权并查集是自己第一次接触，每个点多了一个d[]数组，用来记录这个点到根节点的距离。

废话了一通，这题的关键点在于，1，2操作会把一个点从原有点集中拿出，这样很多点的相对关系就会乱，所以我们每次不把原有点从点集拿出，而是抛弃原有的点，用新的点代替，这样原有点集之间的相对关系就不会乱掉

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> P;
const int MAXN = 2e5 + 5;

P operator+(const P &a, const P &b) { return P(a.first + b.first, a.second + b.second); }
P operator-(const P &a, const P &b) { return P(a.first - b.first, a.second - b.second); }
bool operator!=(const P &a, const P &b) { return a.first != b.first || a.second != b.second; }

int n;
int pa[MAXN], r[MAXN];
int node_num;
P d[MAXN];

int findset(int x) {
  if (pa[x] != x) {
    int root = findset(pa[x]);
    d[x] = d[x] + d[pa[x]];
    return pa[x] = root;
  } else return x;
}

int newnode() {
  pa[node_num] = node_num;
  d[node_num] = P(0, 0);
  return node_num++;
}

int main() {
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  int T, kase = 0;
  scanf("%d", &T);
  while (T--) {
    printf("Case #%d:n", ++kase);
    scanf("%d", &n);
    node_num = 0;
    for (int i = 0; i <= n; ++i) r[i] = newnode();
//    for (int i = n + 1; i <= n << 1; ++i) d[i] = P(0, 0);
    int op, a, b, x, y, now, fa, fb;
    for (int i = 1; i <= n; ++i) {
      scanf("%d%d", &op, &a);
      b = 0;
      if (op == 1 || op == 2) {
        if (op == 1) scanf("%d%d%d", &b, &x, &y);
        else scanf("%d%d", &x, &y);
        r[a] = newnode();
        a = r[a]; b = r[b];
        fb = findset(b);
        pa[a] = fb;
        d[a] = P(x, y) + d[b];
      } else if (op == 3 || op == 4) {
        if (op == 3) scanf("%d%d%d", &b, &x, &y);
        else scanf("%d%d", &x, &y);
        a = r[a]; b = r[b];
        fa = findset(a); fb = findset(b);
        if (fa == fb) {
          if ((d[a] - d[b]) != P(x, y)) puts("REJECT");
        } else {
          pa[fa] = fb;
          d[fa] = d[b] - d[a] + P(x, y);
        }
      } else if (op == 5 || op == 6) {
        if (op == 5) scanf("%d", &b);
        a = r[a]; b = r[b];
        fa = findset(a); fb = findset(b);
        if (fa != fb) puts("UNKNOWN");
        else printf("%d %dn", d[a].first - d[b].first, d[a].second - d[b].second);
      }
    }
  }
}