pku1751.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 85 行

#include <stdio.h>
#define SZ 800
#define TheMax 100000001

typedef struct 
{
	int dis;
	int id;
	int st;
} DDD;


DDD mindis[SZ];
int x[800], y[800];
int Dis[SZ][SZ];
int N, K;

void pre()
{
	int i, j;
	for (i = 1; i <= N ; i++)
	{
		for (j = 1; j < i; j++)
		{
			Dis[i][j] = Dis[j][i] = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
		}
		Dis[i][i] = 0;
	}
}

void Prim()
{
	int i, j, u, min;

	for (i = 2; i <= N; i++)
	{
		mindis[i].dis = Dis[i][1];
		mindis[i].id = 1;
		mindis[i].st = 0;
	}
	mindis[1].st = 1;
	
	for (i = 1; i < N; i++)
	{
		min = TheMax;
		u = -1;
		for (j = 1; j <= N; j++)
		{
			if (!mindis[j].st && mindis[j].dis < min)
			{
				min = mindis[j].dis;
				u = j;
			}
		}
		mindis[u].st = 1;
		if (min) printf("%d %d\n", u, mindis[u].id);
		for (j = 1; j <= N; j++)
		{
			if (!mindis[j].st && mindis[j].dis > Dis[u][j])
			{
				mindis[j].dis = Dis[u][j];
				mindis[j].id = u;
			}
		}
	}
}

int main()
{
	int i, j, s, e;
	scanf("%d", &N);
	for (i = 1; i <= N; i++)
	{
		scanf("%d%d", x + i, y + i);
	}
	pre();
	scanf("%d", &K);
	for (i = 0; i < K; i++)
	{
		scanf("%d %d", &s, &e);
		Dis[s][e] = Dis[e][s] = 0;
	}
	Prim();
	return 0;
}