题解：UVA1329 Corporative Network

UVA1329 Corporative Network

题目大意

给定一张无向图，要求支持下面两种操作（初始状态没有边）：

• I x y：将 y 设为 x 的父节点，边 x -> y 的长度为 $|x-y|$ 对 $1000$ 取模后的值；
• E x：查询 x 到其根节点的距离。

解题思路

方法一

在本题的数据范围下，基础的模拟+递归可以在不使用任何优化的情况下通过，但用时较长。此方法不够优雅，故代码略去。

方法二

使用带权并查集。

在普通的并查集基础上，额外记录每个结点到其当前父节点的距离。在执行 find 操作时，返回祖先节点的同时一路更新路径上所有点到父节点的距离。详见代码。

参考代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
// #include<unordered_map>
// #define map unordered_map
#ifdef ONLINE_JUDGE
#    define getchar getchar_unlocked
#endif
using namespace std;
/*================*/

inline int read() {
    char c = getchar();
    int  x = 0, f = 1;
    for (; !isdigit(c); c = getchar())
        if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    return x * f;
}

#define r(a) (a) = read()
#define MAXN 20005

int T;
int N, I, J;
struct node {
	int fa, dis;
} data[MAXN];
char op[5];

int find(int x) {
	if (data[x].fa == x)
		return x;
	else {
		int root = find(data[x].fa);
		data[x].dis = data[x].dis + data[data[x].fa].dis;
		return data[x].fa = root;
	}
}

void solve() {
	for (int i = 1; i <= N; i++)
		data[i] = {i, 0};
	while (1) {
		scanf("%s", op);
		if (op[0] == 'O')
			break;
		else if (op[0] == 'E') {
			r(I);
			find(I);
			printf("%d\n", data[I].dis);
		}
		else {
			r(I); r(J);
			data[I].fa = J;
			data[I].dis = abs(I - J) % 1000;
		}
	}
}

signed main() {
	r(T);
	while (T--) {
		r(N);
		solve();
	}
	return 0;
}