Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:用并查集做的 Why wrong?期待高手指点

Posted by newton88518 at 2006-11-13 16:11:27 on Problem 3065
In Reply To:用并查集做的 Why wrong?期待高手指点 Posted by:newton88518 at 2006-11-12 13:07:04
> #include<stdio.h>
> #include<string.h>
> #include<math.h>
> #include<stdlib.h>
> #define N 6000001
> int v[N],d[N],n;
> int findd(int p)
> {
> 	int i;
> 	for(i=p;i!=v[i];i=v[i])
> 		v[i]=v[v[i]];
> 	return i;
> }
> void linkp(int pa,int pb)
> {
> 	pa=findd(pa);
> 	pb=findd(pb);
> 	if(pa==pb) return;
> 	if(d[pa]>d[pb]) 
> 	{
> 		v[pb]=pa;
> 		d[pa]+=d[pb];
> 	}
> 	else 
> 	{
> 		v[pa]=pb;
> 		d[pb]+=d[pa];
> 	}
> }
> int suma,sumb;
> bool judge(int pa,int pb)
> {
> 	pa=findd(pa);
> 	pb=findd(pb);
> 	if(pa==pb) {
> 		suma++;
> 		return 1;
> 	}
> 	sumb++;
> 	return 0;
> }
> void init()
> {
> 	int i;
> 	for(i=1;i<=n;i++)
> 	{
> 		v[i]=i;
> 		d[i]=1;
> 	}
> }
> int main()
> {
> 	//freopen("a.in","r",stdin);
> 	char s[300],g[10];
> 	int r[5],k=0,i;
> 
> 	while(gets(s))
> 	{
> 		 k=0;
> 		 i=1;
> 		 while(sscanf(s+i,"%s",g)!=EOF)
> 		 {
> 			 do ++i;
> 			 while(s[i]==' ');
> 			 i+=strlen(g);
> 			 r[k]=atoi(g);
> //			 printf("%d ",r[k]);
> 			 k++;
> 		 }
> //		 printf("\n");
> 		 if(s[0]=='c' || s[0]=='C')
> 		 {
> 			 if(k==2) linkp(r[0],r[1]);
> 			 else if(k==3)
> 			 {
> 				 for(i=0;i<r[2];i++)
> 					 linkp(r[0],r[1]+i);
> 			 }
> 			 else if(k==4)
> 			 {
> 				 if(r[3]==0) linkp(r[0],r[1]);
> 				 else 
> 				 for(i=0;i<r[2];i++)
> 				 {
> 					 linkp(r[0],r[1]);
> 					 r[1]+=r[3];
> 				 }
> 			 }
> 			 else 
> 			 {
> 				 if(r[3]==0 && r[4]==0) linkp(r[0],r[1]);
> 				 else 
> 				 for(i=0;i<r[2];i++)
> 				 {
> 					 linkp(r[0],r[1]);
> 					 r[0]+=r[4];
> 					 r[1]+=r[3];
> 				 }
> 			 }
> 		 }
> 		 else if(s[0]=='q' || s[0]=='Q')
> 		 {
> 			 suma=sumb=0;
> 			 if(k==2) judge(r[0],r[1]);
> 			 else if(k==3)
> 			 {
> 				 for(i=0;i<r[2];i++)
> 					 judge(r[0],r[1]+i);
> 			 }
> 			 else if(k==4)
> 			 {
> 				 if(r[3]==0) judge(r[0],r[1]);
> 				 else 
> 				 for(i=0;i<r[2];i++)
> 				 {
> 					 judge(r[0],r[1]);
> 					 r[1]+=r[3];
> 				 }
> 			 }
> 			 else 
> 			 {
> 				 if(r[3]==0 && r[4]==0) judge(r[0],r[1]);
> 				 else 
> 				 for(i=0;i<r[2];i++)
> 				 {
> 					 judge(r[0],r[1]);
> 					 r[0]+=r[4];
> 					 r[1]+=r[3];
> 				 }
> 			 }
> 			 printf("%d - %d\n",suma,sumb);
> 		 }
> 		 else 
> 		 {
> 			 n=r[0];
> 			 init();
> 		 }
> 	}
> 	return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator