POJ 1182 먹이 사슬 [편집]

문제 풀이 사고: 먼저 생각 이 없 는 - 그리고 몇 편의 문제 풀이 보고 서 를 보 았 다.
              http://blog.csdn.net/ditian1027/article/details/20804911
              http://poj.org/showmessage?message_id=152847
              http://blog.163.com/jiazheng2222%40126/blog/static/16963238320101258935104/
이것 은 토론 안의 분석 이다 -

 http://poj.org/showmessage?message_id=152847

      ，            a,b  ，             ，

> 

>                ，              。    

> 

>    2                 ，         ，    

> 

> a->b    0  a b  

> 

> a->b    1  a b

> 

> a->b    2  a b ，   b a

> 

>       ，                          。

> 

>       ，a        aa，b        bb，a->b     d-1（           ）

> 

> (1)  aa bb   ，     bb   aa ，    delta[bb] （delta[i]  i         i    ）

> 

>        aa->bb = aa->a + a->b + b->bb，                

> 

>             ：aa->bb = (delta[a]+d-1+3-delta[b])%3 = delta[bb]，（ 3           [0,2] ）

> 

> (2)  aa bb  ，       a->b              d-1  

> 

>        a->b = a->aa + aa->b = a->aa + bb->b，

> 

>             ：a->b = (3-delta[a]+delta[b])%3，

> 

>           ，    。

> 

>      LS     :]

　　
              다음은 자신의 체험 이다.

pre[x]：  x     pre[x]

p=find(x),  p  x    

relation[x] :    x        ，

             relation[x]=p->x(         ，             ，relation[x]        p  x   )

             relation[x]=0   p x  

             relation[x]=1   p x

			 relation[x]=2   x p 

----------------------------------------------------------------------------------- 

         d,x,y

    x,y          (         x,y      )

 if(x,y      )

 {

 	           ;

 } 

 else

 {

 	       ， x,y    ;

 }

----------------------------------------------------------------------------------- 

                 

 (   )           ，                ，      

 1)

 d==1   x,y    

 relation[x]    relation[y]

    0               0

    1               1

    2               2

    relation[x]!=relation[y]，       

2）

d==2   x y

relation[x]    relation[y]

    0               2     //  x      ，  x y,relation[y]=2 

    2               1     //  x    ，  x y, y      ，relation[y]=1 

    1               0     //  x     ，  x y, y      ，relation[y]=1

             ，       





(   )

    http://poj.org/showmessage?message_id=152847

      

x->y=x->p+p->y//    p=q,     p  q

    =-relation[x]+relation [y]

    =relation[y]-relation[x]//      ，             ，    3，

	=(relation[y]-relation[x]+3)%3 //         0 2  ，       3

          d==1 x,y   ，           0，   d-1

                           ，     ，      

 

((relation[y]-relation[x]+3)%3) !=d-1,       



--------------------------------------------------------------------------------------- 

  p,q        x,y

 q   p ，    relation[q] 

p->q=p->x+x->y+y->q

    =relation[x]+(d-1) +(-relation[y])//            ，  3 

    =(relation[x]-relation[y]+(d-1)+3) %3//         0 2  ，  3 

  relation[q]=(relation[x]-relation[y]+(d-1)+3) %3



----------------------------------------------------------------------------------------

       ，    relation[]  

   ：http://blog.csdn.net/ditian1027/article/details/20804911

        x,      fx,    ffx,  ffx->x

  ffx->x=ffx->fx+fx->x

         =relation[fx]+relation[x]



  relation[x]=(relation[x]+relation[tmp])%3 

 fx  x     ，   find()         ，     ，x       fx',       

       fx   ，   tmp      ，   

---------------------------------------------------------------------------------------- 

반성: relation [] 배열 을 벡터 로 표시 할 때 벡터 출발점 과 벡터 의 종점 은 반드시 밝 혀 야 한다. 그렇지 않 으 면 뒤의 식 기호 가 틀 릴 것 이다.
다음은 말의 진 위 를 판단 하 는 두 가지 코드 입 니 다.
 

#include<stdio.h>

#define maxn 50010

int pre[maxn],relation[maxn];

int find(int a)

{

	int tmp;

	tmp=pre[a];

	if(a!=pre[a])

	pre[a]=find(pre[a]);

	relation[a]=(relation[a]+relation[tmp])%3;

	return pre[a];

}



void unionroot(int x,int y,int d)

{

	int p,q;

	p=find(x);

	q=find(y);

	pre[q]=p;

	relation[q]=(relation[x]-relation[y]+3+d-1)%3;

}



int main()

{

	int i,n,k,sum,x,y,p,q,d;

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

		for(i=0;i<=maxn;i++)

		{

			pre[i]=i;

			relation[i]=0;

		}

		sum=0;

		while(k--)

		{

			scanf("%d %d %d",&d,&x,&y);

			p=find(x);

			q=find(y);

			if((x>n||y>n)||(x==y&&d==2))

			{

			sum++;

			continue;

		    }

			if(p==q)

			{

				if((relation[y]-relation[x]+3)%3!=d-1)

					 sum++;

			}

				else

				unionroot(x,y,d);

		}

		printf("%d
",sum);

}

　　
 

#include<stdio.h>

#define maxn 50010

int pre[maxn],relation[maxn];

int find(int a)

{

	int tmp;

	tmp=pre[a];

	if(a!=pre[a])	

	pre[a]=find(pre[a]);

	relation[a]=(relation[a]+relation[tmp])%3;

	return pre[a];		

}



void unionroot(int x,int y,int d)

{

	int p,q;

	p=find(x);

	q=find(y);

	pre[p]=q;

	relation[p]=(relation[y]-relation[x]+3+d-1)%3;

}



int main()

{

	int i,n,k,sum,x,y,p,q,d;

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

		for(i=0;i<=maxn;i++)

		{

			pre[i]=i;

			relation[i]=0;

		}

		sum=0;

		while(k--)

		{

			scanf("%d %d %d",&d,&x,&y);

			p=find(x);

			q=find(y);

			if((x>n||y>n)||(x==y&&d==2))

			{

			sum++;

			continue;

		    }	

			if(p==q)				

			{

				if(d==1&&relation[x]!=relation[y])

				++sum;

				if(d==2)

				{

					if(relation[x]==0&&relation[y]!=2)

					++sum;

					if(relation[x]==1&&relation[y]!=0)

					++sum;

					if(relation[x]==2&&relation[y]!=1)

					++sum;					

				}

								

				

			}

				else  

				unionroot(x,y,d);

		}

		printf("%d
",sum);

}