ZOJ 1914 Arctic Network （POJ 2349 UVA 10369） MST

题目大意，给定一些点的坐标，求MST，然后要求求去掉最大的k条边后，最大的边

直接Prim，然后在排序即可。

小技巧是一开始不求平方根，最后输出的时候在求出平方根即可。

ZOJ上排行第三，不过在POJ就被虐了。。。

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int MAXN=501;

const int INF=9999999;

int map[MAXN][MAXN];

double dis[MAXN];

struct point

{

	int x,y;

}ship[MAXN];

void prim(int n)

{

	int i,j;

	for(i=1;i<=n;i++)

		dis[i]=INF;

	bool vis[MAXN]={0};

	int cur=1;

	vis[cur]=1;

	dis[cur]=0;

	for(i=1;i<=n;i++)

	{

		double mini=INF;

		for(j=1;j<=n;j++)

			if(!vis[j] && dis[j] > map[cur][j])

				dis[j]=map[cur][j];

		for(j=1;j<=n;j++)

			if(!vis[j] && mini > dis[j])

				mini=dis[cur=j];

		vis[cur]=true;

	}

}

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		int n,x;

		scanf("%d%d",&x,&n);

		int i,j;

		for(i=1;i<=n;i++)

			scanf("%d%d",&ship[i].x,&ship[i].y);

		for(i=1;i<=n;i++)

		{

			for(j=1;j<=n;j++)

			{

				map[i][j]=	map[j][i] =

					(ship[j].y -ship[i].y) *(ship[j].y -ship[i].y) + (ship[j].x -ship[i].x)*(ship[j].x -ship[i].x);

			}

		}

		prim(n);

		sort(dis+1,dis+n+1);

		printf("%.2lf\n",sqrt(dis[n-x+1]));

	}

	return 0;

}

巴特西

ZOJ 1914 Arctic Network （POJ 2349 UVA 10369） MST

最新文章

热门文章