亚洲人成小说网站色在线,99热精品在线,国产精品每日更新

對于蝸牛來說，狂奔雖不代表極速，但展現的卻是一種拼盡全力的姿態........

pku 1182

2009年7月12日星期日

題目鏈接：PKU 1182 食物鏈

分類：并查集的拓展（經典）

題目分析與算法模型

本題是一道經典的并查集的拓展，其中比較一般的解法是設立三個group，因為一共有三種動物。但其實有一種更加簡便的方法，具體如下，利用向量的思考模式將三個group合并成一個并查集，同時對每個節點保持其到根結點的相對類別偏移量，定義為：
0——同類；
1——食物；
2——天敵；
對于樹中的每一個節點（動物），記錄其與根節點的相對偏移量，即上面的0，1和2，這樣就可以根據相對平移量計算出其和根節點所代表的動物的關系，合并節點時，注意兩棵樹的根節點之間的相對偏移量，這里有幾個公式需要自己推導，都在代碼中了；

Code：

1

#include<stdio.h>
2

#define max 50005
3

4

int n,k,i,j,parent[max],kind[max],count,a,b,d;
5

6

void init(int n)
7

{
8

for(j=1;j<=n;j++)
9

{
10

parent[j]=-1;
11

kind[j]=0;
12

}
13

}
14

int find(int x)
15

{
16

int t=parent[x];
17

if(t<0)return x;
18

parent[x]=find(t);
19

kind[x]=(kind[x]+kind[t])%3;
20

return parent[x];
21

}
22

void Union(int x,int y,int d)
23

{
24

if(x>n||y>n)count++;
25

else if(d==1)
26

{
27

int root1=find(x),root2=find(y);
28

if(root1==root2)
29

{
30

if(kind[x]!=kind[y])count++;
31

}
32

else
33

{
34

if(parent[root1]<parent[root2]) //root1為根
35

{
36

parent[root1]+=parent[root2];
37

parent[root2]=root1;
38

kind[root2]=(kind[x]-kind[y]+3)%3; //需要自己推導
39

}
40

else //root2為根
41

{
42

parent[root2]+=parent[root1];
43

parent[root1]=root2;
44

kind[root1]=(kind[y]-kind[x]+3)%3;
45

}
46

}
47

}
48

else //d=2
49

{
50

if(x==y)count++;
51

else
52

{
53

int root1=find(x),root2=find(y);
54

if(root1==root2)
55

{
56

if(kind[x]!=(kind[y]+1)%3)count++; //需要自己推導
57

}
58

else
59

{
60

if(parent[root1]<parent[root2]) //root1為根
61

{
62

parent[root1]+=parent[root2];
63

parent[root2]=root1;
64

kind[root2]=(kind[x]-kind[y]+5)%3; //需要自己推導
65

}
66

else //root2為根
67

{
68

parent[root2]+=parent[root1];
69

parent[root1]=root2;
70

kind[root1]=(kind[y]-kind[x]+4)%3; //需要自己推導
71

}
72

}
73

}
74

}
75

}
76

int main()
77

{
78

scanf("%d%d",&n,&k);
79

init(n);
80

count=0;
81

for(i=0;i<k;i++)
82

{
83

scanf("%d%d%d",&d,&a,&b);
84

Union(a,b,d);
85

}
86

printf("%d\n",count);
87

return 0;
88

}
89

posted on 2009-07-13 00:08 蝸牛也Coding 閱讀(1217) 評論(3) 編輯收藏引用

# re: pku 1182[未登錄] 2009-12-17 12:12 YY

# re: pku 1182 2010-02-12 16:04 Y

# re: pku 1182[未登錄] 2010-03-26 19:15 菜鳥

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

pku 1182

評論

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理