> /*pku 1751*/
> #include<stdio.h>
> #include<string.h>
> #include<stdlib.h>
> #define N 755
> int coordinates[N][2];
> int find[N];
> int father[N];
> int n,tree_num,out_num,find_num;
> struct CONNECT
> {
> 	int begin,end;
> 	int dis;
> }connect[N*N/2];
> 
> struct CREAT
> {
> 	int begin,end;
> }creat[N*N/2];
> 
> 
> int find_father(int a)
> {
> 	if(father[a]!=a)	
> 		father[a]=find_father(father[a]);
> 
> 	return father[a];
> }
> 
> int cmp(const void *a,const void *b)
> {
> 	return (*(struct CONNECT *)a).dis-(*(struct CONNECT *)b).dis;
> }
> 
> 
> void kruskal()
> {
> 	int ii,jj,tmp1,tmp2,ans;
> 	ans=-1,jj=1;
> 	while(1)
> 	{
> 		while(1)
> 		{
> 			tmp1=find_father(connect[jj].begin);
> 			tmp2=find_father(connect[jj].end);
> 			if(tmp1!=tmp2)/*看他们是不是已经连在一起了里*/
> 				break;
> 			else
> 				jj++;
> 		}
> 		
> 
> 		father[tmp1]=tmp2;
> 
> 		creat[++ans].begin=connect[jj].begin;/*将找到的边存起来，一次性输出*/
> 		creat[ans].end=connect[jj].end;
> 				
> 		if(!find[creat[ans].begin])
> 		{
> 			find[creat[ans].begin]=1;
> 			find_num++;
> 		}
> 		if(!find[creat[ans].end])
> 		{
> 			find[creat[ans].end]=1;
> 			find_num++;
> 		}
> 
> 		if(find_num==n)
> 		{	
> 			out_num=ans;
> 			break;
> 		}
> 		
> 	}
> 	
> }
> 
> int main()
> {
> 	int ii,jj,kk;
> 	int a,b,m;
> 	int d;
> 	int tmp1,tmp2;
> 		scanf("%d",&n);
> 		
> 		for(ii=1;ii<=n;ii++)
> 			father[ii]=ii,find[ii]=0;
> 		
>         for(ii=1,kk=0;ii<=n;ii++)
> 		{
> 				scanf("%d%d",coordinates[ii],coordinates[ii]+1);
> 				for(jj=1;jj<ii;jj++)
> 				{/*求任意两点的距离*/
> 					connect[++kk].dis=(coordinates[ii][0]-coordinates[jj][0])*(coordinates[ii][0]-coordinates[jj][0])
> 						+(coordinates[ii][1]-coordinates[jj][1])*(coordinates[ii][1]-coordinates[jj][1]);
> 					connect[kk].begin=jj,connect[kk].end=ii;
> 				}
> 		}
> 
> 		find_num=0;
> 		scanf("%d",&m);
> 		
> 		for(ii=1;ii<=m;ii++)
> 		{	
> 			scanf("%d%d",&a,&b);
> 			if(!find[a])
> 			{
> 				find[a]=1;
> 				find_num++;
> 			}
> 			if(!find[b])
> 			{	
> 				find[b]=1;
> 				find_num++;
> 			}
> 			tmp1=find_father(a);
> 			tmp2=find_father(b);
> 			if(tmp1!=tmp2)
> 				father[tmp1]=tmp2;
> 		}
> 		
> 		if(find_num==n)/*如果所有点都找到就退出*/
> 			return 1;
> 	
> 		tree_num=kk;
> 
> 		qsort(&connect[1],tree_num,sizeof(connect[1]),cmp);/*将所有的边按从小到大排列*/
> 
> 		kruskal();
> 		
> 
> 
> 		for(ii=0;ii<=out_num;ii++)
> 			printf("%d %d\n",creat[ii].begin,creat[ii].end);
> 
> 		return 1;
> }
> 
> 
> 

• 做题太不冷清，犯了一个错误，唉，白白的WA了那么多次 (0) xiangsanzi 2006-04-05 13:25:00