食物链

北大oj1182

rank[x]=

0 表示节点x与father[x]为同类

1 表示节点x吃father[x]

2 表示x被father[x]吃

向量的思考模式

AB=rank[a],CB=rank[c];BC=-rank[c]; a与c的关系为rank[a]-rank[c];

判断两个节点点a, b的关系

. （1）如果ra != rb，说明a, b暂时没有关系，那么关于他们的判断都是正确的，然后合并这两个子树。这里是关键，如何合并两个子树使得合并后的新树能保证正确呢？（将a所在的子树合并到b上）

s表示 a与b的关系

s=rank[a]+rank[f1]-rank[b]

rank[f1]= s-rank[a]+rank[b]

void union_set (int a,int b,int s)

{

int f1=find_set(a);

int f2=find_set(b);

father[f1]=rb;

rank[f1]=(s - rank[a] + rank[b] + 3)%3;

}

•(2)如果f1 =f2说明a, b之前已经有关系了。那么我们就判断语句是否是对的

•同样根据向量的思考模式转化为

• rank[a]-rank[b]==s 进行判断

路径压缩：

int find_set(int x)

{

int t;

if(x==father[x]) return x;

else {

t=father[x]; father[x]=find_set(father[x]);

rank[x]=(rank[x]+rank[t])%3; （根据向量模式）

return father[x];

}

具体看代码

View Code

 1 //食物链1182
 2 #include<stdio.h>
 3 int father[50001],rank[50001];
 4 int find(int x)
 5 {
 6     int t;
 7     if(father[x]==x)
 8         return x;
 9     else
10     {
11         t=father[x];
12         
13         father[x]=find(father[x]);
14     rank[x]=(rank[x]+rank[t])%3;
15     return father[x];
16     }
17 }
18 void Union(int x,int y,int s)
19 {
20     int f1=find(x);
21     int f2=find(y);
22     father[f1]=f2;
23     rank[f1]=(rank[y]-rank[x]+s+3)%3;
24 }
25 int main()
26 {
27     int n,m,s,x,y,f1,f2,i,j,num;
28      scanf("%d%d",&n,&m);
29 
30         for(i=1;i<=n;i++)
31         {
32             father[i]=i;
33             rank[i]=0;
34         }
35         num=0;
36         for(j=1;j<=m;j++)
37         {
38             scanf("%d%d%d",&s,&x,&y);
39             if(x>n||y>n||(s==2&&x==y))
40                 num++;
41             else
42             {
43                 f1=find(x);
44                 f2=find(y);
45                 if(f1==f2)
46                 {
47                     if((rank[x]-rank[y]+3)%3!=s-1)
48                         num++;
49                 }
50                 else
51             
52                     Union(x,y,s-1);
53             
54             }
55         }
56             printf("%d\n",num);
57         
58 
59     return 0;
60 }
61 /*
62 100 7
63 1 101 1 
64 2 1 2
65 2 2 3 
66 2 3 3 
67 1 1 3 
68 2 3 1 
69 1 5 5
70 */