2149148_wa.c

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

# include <stdio.h>
# define MAX 1001
# define INF 100000000

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

	max = -1;
	for(i = 0; i < n; i++)
	{
		lowcost[i][0] = cost[v][i];
		lowcost[i][1] = v;
		closest[i] = v;
	}
	for(i = 1; i < n; i++)
	{
		min = INF;
		for(j = 0; j < n; j++)
			if(lowcost[j][0]!=0&&lowcost[j][0]<min)
			{
				min = lowcost[j][0];
				k = j;
			}
		E[i-1][1] = k>lowcost[k][1]?k:lowcost[k][1];
		E[i-1][0] = k<lowcost[k][1]?k:lowcost[k][1];
		if(min>max)
			max = min;
		lowcost[k][0] = 0;
		for(j = 0; j < n; j++)
			if(cost[k][j]!=0&&cost[k][j]<lowcost[j][0])
			{
				lowcost[j][0] = cost[k][j];
				lowcost[j][1] = k;
				closest[j] = k;
			}
	}
	printf("%ld\n%d\n",max,n-1);
	for(i = 0; i < n-1; i++)
		printf("%d %d\n",E[i][0]+1,E[i][1]+1);
}

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

	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			cost[i][j] = 0;
	for(i = 0; i < e; i++)
	{
		scanf("%d%d%d",&v1,&v2,&w);
		cost[v1-1][v2-1] = cost[v2-1][v1-1] = w;
	}
}
int main()
{
	int n, e;
	long cost[MAX][MAX];

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