#include<stdio.h>
#include<math.h>

#define MAX 800
#define MAX_VALUE 100000000

struct _node
{
	int x;
	int y;
};

struct _aaa
{
	int s;
	int e;
};

struct _bbb
{
	int pre;
	float we;
};

typedef struct _aaa aaa;
typedef struct _bbb bbb;
typedef struct _node node;

bbb flag[MAX];
node town[MAX];
float map[MAX][MAX];
aaa result[MAX];

int town_count = 0;
int exist = 0;
int start = 0;

int main(void)
{
	int i = 0;
	int j = 0;
	
	scanf("%d",&town_count);

	for(i = 0; i < town_count; ++i)
	{
		scanf("%d %d",&town[i].x,&town[i].y);
	}

	for(i = 0; i < town_count; ++i)
	{
		for(j = 0; j < town_count; ++j)
		{
			if( i == j )
			{
				map[i][j] = 0;
				continue;
			}

			map[i][j] = (float)sqrt( ( town[i].x - town[j].x ) * ( town[i].x - town[j].x ) +  ( town[i].y - town[j].y ) * ( town[i].y - town[j].y ) );
		}
	}

	scanf("%d",&exist);

	for(i = 0; i < exist; ++i)
	{
		int x = 0;
		int y = 0;
		scanf("%d %d",&x,&y);
		map[x-1][y-1] = 0.01f;
		map[y-1][x-1] = 0.01f;
		start = x - 1;
	}


	for(i = 0; i < town_count; ++i)
	{
		flag[i].pre = start;
		flag[i].we = map[i][start];
	}

	flag[start].we = 0;
	
	float min = 0;
	int k = -1;
	int len = 0;

	for(i = 0; i < town_count - 1; ++i)
	{
		min = MAX_VALUE;
		for(j = 0; j < town_count; ++j)
		{
			if( flag[j].we != 0 && flag[j].we < min )
			{
				min = flag[j].we;
				k = j;
			}
		}
		
		if( map[k][flag[k].pre] - 0.01 > 0 )
		{
			result[len].s = flag[k].pre;
			result[len].e = k;
			++len;
		}

		for(j = 0; j < town_count; ++j)
		{
			if( map[j][k] < flag[j].we )
			{
				flag[j].we = map[j][k];
				flag[j].pre = k;
			}
		}
	}
	
	for(i = 0; i < len; ++i)
	{
		printf("%d %d\n",result[i].e + 1,result[i].s + 1);
	}
	

	return 0;
}

• Re:总有人前赴后继的贴代码,,,,FT,,,不知是炫耀还是.... (2075) GetAC 2008-08-28 15:20:40
  • Re:总有人前赴后继的贴代码,,,,FT,,,不知是炫耀还是.... (6) luoguangyao 2009-03-22 14:06:17
    • 写的又长又难看还好意思来贴。 (2) jiangmingh 2009-05-10 20:26:30
• Re:哈哈，就是最小生成树啊。 贴贴源程序了。 (53) teqiji 2009-09-21 21:36:23
• 贴在自己博客好一点 (0) DestinyDesigner 2009-09-21 23:48:18
  • Re:贴在自己博客好一点 (0) acm_newer 2009-09-22 08:09:46
• Re:哈哈，就是最小生成树啊。 贴贴源程序了。 (6) wust_zhanpang 2014-07-08 19:22:33