UVa 1329 - Corporative Network Union Find题解

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


UVa 1329 - Corporative Network Union Find题解,布布扣,bubuko.com

UVa 1329 - Corporative Network Union Find题解

上一篇:XStream互转String和XML,以及如何读取web的下的文件


下一篇:【web开发学习笔记】Structs2 Result学习笔记(一)简单介绍