2091143_wa.c

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

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

long W;
void prim(int n, long cost[][MAX],int v)
{
	int i, j, k;
	long min;
	long lowcost[MAX];
	long 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("%ld\n",W);
}

void init(int n,long cost[][MAX])
{
	int i, j;

	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			scanf("%ld",&cost[i][j]);
}
int main()
{
	int n;
	long cost[MAX][MAX];

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