/*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;
}

• 哪位好人帮忙一下啊 (2560) xiangsanzi 2006-04-04 19:27:03
  • 做题太不冷清，犯了一个错误，唉，白白的WA了那么多次 (0) xiangsanzi 2006-04-05 13:25:00