2569179_ac_15ms_96k.cpp

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

# include <stdio.h>
# include <stdlib.h>

# define MAXV 100
# define MAXE 1000

int map[MAXV][MAXV];

typedef struct enode
{
	int v1;
	int v2;
	int weight;
}Edge;

Edge E[MAXE];
int vest[MAXV];
int cmp(const void *a, const void *b)
{
	struct enode *aa = (struct enode *)a;
	struct enode *bb = (struct enode *)b;
	if(bb->weight!=aa->weight)
		return aa->weight-bb->weight;
	else
		if(aa->v1!=bb->v1)
			return aa->v1-bb->v1;
		else
			return aa->v2-bb->v2;
}

void kruskal(int n,int e)
{
	int i, k, j;
	int m1, m2, sn1, sn2;

	for(i = 0; i < n; i++)
		vest[i] = i;
	k = 1;
	j = 0;
	while(k < n&&j<e)
	{
		m1 = E[j].v1; m2 = E[j].v2;
		sn1 = vest[m1]; sn2 = vest[m2];
		if(sn1!=sn2)
		{
			printf("%c-%c %d\n",m1+'A',m2+'A',E[j].weight);
			k++;
			for(i = 0; i < n; i++)
				if(vest[i]==sn2)
					vest[i] = sn1;
		}
		j++;
	}
}


int main()
{
	int i, t, j;
	int n, e, cas = 1;

	scanf("%d",&t);
	while(t--)
	{
		printf("Case %d:\n",cas++);
		scanf("%d",&n);
		e = 0;
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
			{
				scanf("%d",&map[i][j]);
				getchar();
				if(map[i][j]&&i>j)
				{
					E[e].v1 = j;E[e].v2 = i;
					E[e].weight = map[i][j];
					e++;
				}
			}
		qsort(E,e,sizeof(E[0]),cmp);
		kruskal(n,e);
	}
	return 1;
}