這是一題相當有水平的并查集問題。雖然我一次性ac，但是基本上是沒有任何思路搜索了一下牛人思路才過的。
思考這題時，我陷入到了以下怪圈：
1.并查集應該是無限的，但是貌似這題的并集只有三個
2.當兩者關系未被確認是哪個集合時，會出現無限多的臨時子集
3.如何表示臨時子集
看了看牛人的思路，相當巧妙：并查集基本還是無限集，有限集用關系向量來表示。
1.使用關系向量的方法，讓我獲益匪淺。
2.計算關系向量的方法，又如此的巧合。
3.并查集并不一定是相同的才并一起，又回歸到第一點，當關系向量可以用有限集表示時，并查集里的元素可以不是同一類元素。
最后還要說，這題相當牛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)
評論(0) 編輯 收藏 引用