在我還有一口氣的時候他終于過了........
1
#include<iostream>
2#define MaxN 50000
3typedef struct {
4 int parent;
5 int rank;
6 int food;//指向食物類
7 int enemy;//指向天敵類
8}NODE;
9NODE animal[MaxN+1];
10void init(int n)
11{
12 int i;
13 for(i=1;i<=n;i++){
14 animal[i].parent=i;
15 animal[i].rank=0;
16 animal[i].food=-1;
17 animal[i].enemy=-1;
18 }
19}
20int find_set(int x)
21{
22 if(x==-1)return -1;//有些food，enemy指向-1
23 if(animal[x].parent!=x)
24 animal[x].parent=find_set(animal[x].parent);
25 return animal[x].parent;
26}
27int union_set(int x,int y)
28{
29 if(x==-1)return y;
30 if(y==-1)return x;
31 if(animal[x].rank>animal[y].rank){
32 animal[y].parent=x;
33 return x;}
34 else {
35 animal[x].parent=y;
36 if(animal[x].rank==animal[y].rank)animal[y].rank++;
37 return y;}
38}
39void make(int x,int y,int fx,int fy,int ex,int ey)//創建x吃y的關系
40{
41 int t,v,w;
42 t=union_set(fx,y);//首先將y與x的food合并
43 v=union_set(x,ey);
44 w=union_set(ex,fy);
45 animal[v].enemy=w;
46 animal[v].food=t;
47 animal[t].enemy=v;
48 animal[t].food=w;
49 if(w!=-1){
50 animal[w].food=v;
51 animal[w].enemy=t;}
52}
53int main()
54{
55 int N,K,i,wn=0,x,y,fx,fy,ex,ey,oper;
56 int t,u,v;
57 scanf("%d%d",&N,&K);
58 init(N);
59 for(i=1;i<=K;i++){
60 scanf("%d%d%d",&oper,&x,&y);//oper為1的時候表示x和y是同類，oper為2的時候表示x吃y
61 if(x>N||y>N){wn++;continue;}
62 x=find_set(x);
63 y=find_set(y);
64 fx=find_set(animal[x].food);//fx可能是-1
65 fy=find_set(animal[y].food);//fy也可能是-1
66 ex=find_set(animal[x].enemy);
67 ey=find_set(animal[y].enemy);
68 if(x==y){if(oper==2)wn++;continue;}//1.x,y同類
69 if(fy==x){wn++;continue;}//3.y吃x
70 if(fx==y){if(oper==1)wn++;continue;}//2.x吃y
71 if(oper==2)make(x,y,fx,fy,ex,ey);//4..x和y尚未產生聯系,創建聯系，首先是x吃y，其次y的food類吃x
72 if(oper==1){//4..x和y尚未產生聯系,創建聯系
73 t=union_set(x,y);
74 u=union_set(fx,fy);
75 v=union_set(ex,ey);
76 animal[t].food=u;
77 animal[t].enemy=v;
78 if(u!=-1){
79 animal[u].enemy=t;
80 animal[u].food=v;}
81 if(v!=-1){
82 animal[v].food=t;
83 animal[v].enemy=u;}}
84 }
85 printf("%d\n",wn);
86 return 0;
87}
if(u!=-1)if(v!=-1)這里折騰了我兩天
posted on 2008-01-31 20:39
zoyi 閱讀(1540)
評論(5) 編輯 收藏 引用 所屬分類:
數據結構