2141606_ac_0ms_132k.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 64 行

# include <stdio.h>
# include <math.h>
# define MAX 101
# define INF 2100000000

double W;

void prim(int n, double cost[][MAX],int v)
{
	int i, j, k;
	double min;
	double lowcost[MAX];
	int closest[MAX];

	W = 0;
	for(i = 0; i < n; i++)
	{
		lowcost[i] = cost[v][i];
		closest[i] = v;
	}
	for(i = 1; i < n; i++)
	{
		min = INF;
		for(j = 0; j < n; j++)
			if(lowcost[j]!=0&&lowcost[j]<min)
			{
				min = lowcost[j];
				k = j;
			}
			W += min;
		lowcost[k] = 0;
		for(j = 0; j < n; j++)
			if(cost[k][j]!=0&&cost[k][j]<lowcost[j])
			{
				lowcost[j] = cost[k][j];
				closest[j] = k;
			}
	}
	printf("%.2lf\n",W);
}

void init(int n,double cost[][MAX])
{
	int i, j;
	double pot[101][2];

	for(i = 0; i < n; i++)
	{
		scanf("%lf%lf",&pot[i][0],&pot[i][1]);
		for(j = 0; j < i; j++)
			cost[i][j] = cost[j][i] = sqrt((pot[i][0]-pot[j][0])*(pot[i][0]-pot[j][0])+(pot[i][1]-pot[j][1])*(pot[i][1]-pot[j][1]));
		cost[i][i] = 0;
	}
}
int main()
{
	int n;
	double cost[MAX][MAX];

	scanf("%d",&n);
	init(n,cost);
	prim(n,cost,0);
	return 1;
}