3597364_ac_94ms_8092k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#define MAX 1001
#define INF 2100000000
 
double W;
double cost[MAX][MAX];
 
void prim(int n,int v)
{
	int i, j, k;
	double min;
	double lowcost[MAX];
 
	W = 0;
	for(i = 0; i < n; i++)
		lowcost[i] = cost[v][i];
	for(i = 1; i < n; i++)
	{
		min = INF;
		for(j = 0; j < n; j++)
			if(lowcost[j]!=-1&&lowcost[j]<min)
			{
				min = lowcost[j];
				k = j;
			}
			W += min;
			lowcost[k] = -1;
		for(j = 0; j < n; j++)
			if(cost[k][j]!=-1&&cost[k][j]<lowcost[j])
				lowcost[j] = cost[k][j];
	}
	printf("%.2lf\n",W);
}
 
double point[MAX][2];
 
double dis(int i,int j)
{
	return sqrt((point[i][0]-point[j][0])*(point[i][0]-point[j][0])+(point[i][1]-point[j][1])*(point[i][1]-point[j][1]));
}
 
void init(int n,int m)
{
	int i, j, x, y;
 
	for(i = 0; i < n; i++)
	{
		scanf("%lf%lf",&point[i][0],&point[i][1]);
	}
	for(i = 0; i < n; i++)
	{
		cost[i][i] = -1;
		for(j = i+1; j < n; j++)
			cost[i][j] = cost[j][i] = dis(i,j);
	}
	for(i = 0; i < m; i++)
	{
		scanf("%d%d",&x,&y);
		x--;y--;
		cost[x][y] = cost[y][x] = 0;
	}
}
int main()
{
	int n, m;
 
	while(scanf("%d%d",&n,&m)==2)
	{
		init(n,m);
		prim(n,0);
	}
	return 1;
}