UVa 1329 - Corporative Network Union Find题解
浏览数：20 /
时间：2015年06月09日
UVa的题目好多，本题是数据结构的运用，就是Union Find并查集的运用。主要使用路径压缩。甚至不需要合并树了，因为没有重复的连线和修改单亲节点的操作。
郁闷的就是不太熟悉这个Oj系统，居然使用库中的abs就会WA，自己写了个abs小函数就过了。
题目：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4075
#include <stdio.h>
const int MAX_N = 20005;
const int MOD = 1000;
//在UVa使用库的abs居然WA，浪费好多时间
inline int abs(int a) { return a < 0? -a : a; }
struct Subset
{
int p, w;
};
Subset subs[MAX_N];
int findParent(int x)
{
if (subs[x].p != x)
{
int p = subs[x].p;
subs[x].p = findParent(subs[x].p);
subs[x].w = (subs[x].w + subs[p].w);
}
return subs[x].p;
}
void initSubs(int N)
{
for (int i = 1; i <= N; i++)
{
subs[i].p = i;
subs[i].w = 0;
}
}
int main()
{
int T, N, i, j;
char cmd;
scanf("%d", &T);
while (T--)
{
scanf("%d", &N);
getchar();
initSubs(N);
while ((cmd = getchar()) && cmd != 'O')
{
if (cmd == 'E')
{
scanf("%d", &i);
subs[i].p = findParent(i);
printf("%d\n", subs[i].w);
}
else
{
scanf("%d %d", &i, &j);
subs[i].w = (abs(j - i))%MOD;
subs[i].p = j;//不存在重复连线和更改parent，故此直接连就ok
}
getchar();
}
}
return 0;
}郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
