hdu 1875通畅工程再续-prim最小生成树

hdu 1875畅通工程再续-prim最小生成树

hdu 1875畅通工程再续

 

邻接矩阵中的数据必须初始化完整

 

#include<iostream>
#include<math.h>
using namespace std;

const double INF=1000000000.0;
double mp[100][100]; 

struct point
{
	int x,y;
} P[100];

double prim(int N)
{
	int i,j,k,mark=1;
	double min,length;
	
	for(i=1;i<=N;i++)
	{
		mp[i][i]=0;                      //重要! 
		mp[0][i]=mp[1][i];
	}
	length=0;
	for(i=2;i<=N;i++)
	{
		min=INF;
		k=1;
		for(j=1;j<=N;j++)
		{
			if(mp[0][j]&&min>mp[0][j])
			{
				min=mp[0][j];
				k=j;
			}
		}
		
		if(k==1) return INF;
		length+=min;
		mp[0][k]=0;
		
		for(j=1;j<=N;j++)
			if(mp[0][j]&&mp[0][j]>mp[k][j])
				mp[0][j]=mp[k][j];
		
	}
	return length;
}

double dist(point x,point y)
{
	return (double)sqrt((double)((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y)));
}

int main()
{
	int i,j,T,N;
	double D,ans;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&N);
		for(i=1;i<=N;i++)
		{
			scanf("%d%d",&P[i].x,&P[i].y);
			for(j=1;j<=i;j++)
			{
				D=dist(P[i],P[j]);
				if(10>D||1000<D)
					mp[i][j]=mp[j][i]=INF;
				else
					mp[i][j]=mp[j][i]=D;
			}
		}
		
		ans=prim(N);
		if(ans<INF) printf("%.1lf\n",100*ans);
		else printf("oh!\n");
	}
	return 0;
}