首页 > 代码库 > POJ 1182 食物链 Union Find题解

POJ 1182 食物链 Union Find题解

Union Find就是所谓的并查集。

本题做的很无语,最后发现居然是输入搞错,一直WA。

不能使用循环接受输入,否则是WA的,气死人,浪费那么多时间就为了这个。

难点:

1 构建关系树

2 构建公式

3 快速更新公式

要抽象思维出什么对应什么的关系和上面是逆关系,就是利用0,1,2构建出父子节点之间的关系值,我是这样去思考构建出准确无误的公式的。

这样的抽象度是挺高的,需要多多训练。


关系到数学和Union Find,难度还是挺高的,网上很多人解法了。

我这里就增加一个按权值更新的优化算法,和网上一般的解法不同的地方就是Union操作吧,具体观看下面的unionTwo()函数。

不过oj的时间提高不多,测试数据不是十分大。


#include <stdio.h>

const int MAX_N = 50001;
int N, K;

struct SubSet
{
	int p, r, rank;
};

SubSet subs[MAX_N];

void initSubs()
{
	for (int i = 1; i <= N; i++)
	{
		subs[i].p = i;
		subs[i].r = 0;
		subs[i].rank = 0;
	}
}

int findParent(int x)
{
	if (subs[x].p != x) 
	{
		int p = subs[x].p;
		subs[x].p = findParent(subs[x].p);
		subs[x].r = (subs[x].r+subs[p].r) % 3;//巧妙的计算关系公式
	}
	return subs[x].p;
}

void unionTwo(int x, int y, int d)
{
	int xroot = findParent(x);
	int yroot = findParent(y);

	d--;	//构造y到x的关系值,因为d的值为1,2,这里先假想关系y为x的孩子,x和y同类,值为0,x吃y,值为1,这样构成一条yroot->y->x->xroot的关系路线图,就方便下面计算了
	if (subs[xroot].rank < subs[yroot].rank)
	{
		subs[xroot].p = yroot;		
		subs[xroot].r = (3-subs[x].r + 3-d + subs[y].r) % 3;
	}//3-subs[x].r为逆转x和xroot的关系值, 3-d为逆转x和y的值
	else
	{
		if (subs[xroot].rank == subs[yroot].rank) subs[xroot].rank++;
		subs[yroot].p = xroot;
		subs[yroot].r = (3-subs[y].r + d + subs[x].r) % 3;
	}//3-subs[y].r为逆转yroot和y的关系值
}

int main()
{
	int d, x, y;
	//本题使用循环就会WA的垃圾while (~scanf("%d %d", &N, &K))
	scanf("%d %d", &N, &K);
	initSubs();
	int lies = 0;
	for (int i = 0; i < K; i++)
	{
		scanf("%d %d %d", &d, &x, &y);
		if (x > N || y > N || (d == 2 && x == y)) lies++;
		else if (findParent(x) == findParent(y))
		{//find的时候已经压缩了路径了
			d--;		//减一后就是y到x的关系值了
			if ((3-subs[x].r + subs[y].r)%3 != d) lies++;
		}
		else unionTwo(x, y, d);
	}
	printf("%d\n", lies);
	return 0;
}