Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:用并查集做的 Why wrong?期待高手指点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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator