這是一題相當(dāng)有水平的并查集問(wèn)題。雖然我一次性ac，但是基本上是沒(méi)有任何思路搜索了一下牛人思路才過(guò)的。
思考這題時(shí)，我陷入到了以下怪圈：
1.并查集應(yīng)該是無(wú)限的，但是貌似這題的并集只有三個(gè)
2.當(dāng)兩者關(guān)系未被確認(rèn)是哪個(gè)集合時(shí)，會(huì)出現(xiàn)無(wú)限多的臨時(shí)子集
3.如何表示臨時(shí)子集
看了看牛人的思路，相當(dāng)巧妙：并查集基本還是無(wú)限集，有限集用關(guān)系向量來(lái)表示。
1.使用關(guān)系向量的方法，讓我獲益匪淺。
2.計(jì)算關(guān)系向量的方法，又如此的巧合。
3.并查集并不一定是相同的才并一起，又回歸到第一點(diǎn)，當(dāng)關(guān)系向量可以用有限集表示時(shí)，并查集里的元素可以不是同一類元素。
最后還要說(shuō)，這題相當(dāng)牛B.
#include "stdio.h"
#define MAX 50001
#define Similar 0
#define Enemy 1
#define Food 2
// Food eat Enemy
// Enemy eat Similar
// Similar eat Food
struct _xtree
{
int parent;
int relation;
}xtree[MAX];
int N, K;
void build()
{
int i;
for (i = 1; i <= N; i++)
{
xtree[i].parent = i;
xtree[i].relation = Similar;
}
}
int find(int i)
{
int p = xtree[i].parent;
if (p != i)
{
xtree[i].parent = find(xtree[i].parent);
xtree[i].relation = (xtree[p].relation + xtree[i].relation) % 3;
}
return xtree[i].parent;
}
int check(int x, int y, int r)
{
int root_x, root_y, root_r;
if (x > N || y > N)
{
return 0;
}
root_x = find(x);
root_y = find(y);
if (root_x == root_y) // x relate y
{
return (xtree[x].relation - xtree[y].relation + 3) % 3 == r ? 1 : 0;
}
else
{
root_r = (xtree[y].relation + r + (3 - xtree[x].relation)) % 3;
xtree[root_x].parent = root_y;
xtree[root_x].relation = root_r;
return 1;
}
}
void main()
{
int op, x, y;
int count = 0;
scanf("%d %d", &N, &K);
build();
while (K--)
{
scanf("%d %d %d", &op, &x, &y);
if (!check(x, y, op == 1 ? Similar : Enemy))
{
count++;
}
}
printf("%d\n", count);
}posted on 2010-08-28 21:11
margin 閱讀(159)
評(píng)論(0) 編輯 收藏 引用