> # include <stdio.h>
> # include <stdlib.h>
> 
> # define MAXV 30
> # define MAXE 80
> 
> typedef struct enode
> {
> 	int v1;
> 	int v2;
> 	int weight;
> }Edge;
> 
> Edge E[MAXE];
> int MSW;
> 
> int cmp(const void *a, const void *b)
> {
> 	struct enode *aa = (struct enode *)a;
> 	struct enode *bb = (struct enode *)b;
> 	return aa->weight-bb->weight;
> }
> 
> void kruskal(Edge E[], int n, int e)
> {
> 	int i, k, j;
> 	int m1, m2, sn1, sn2;
> 	int vest[MAXV];
> 
> 	for(i = 0; i < n; i++)
> 		vest[i] = i;
> 	k = 1;
> 	j = 0;
> 	while(k < n)
> 	{
> 		m1 = E[j].v1; m2 = E[j].v2;
> 		sn1 = vest[m1]; sn2 = vest[m2];
> 		if(sn1!=sn2)
> 		{
> 			k++;
> 			MSW += E[j].weight;
> 			for(i = 0; i < n; i++)
> 				if(vest[i]==sn2)
> 					vest[i] = sn1;
> 		}
> 		j++;
> 	}
> }
> 
> int get_graph(int n)
> {
> 	int N, e, weight;
> 	char v1,  v2;
> 
> 	n--; e = 0;
> 	while(n--)
> 	{
> 		getchar();
> 	    scanf("%c%d",&v1,&N);
> 		while(N--)
> 		{
> 			getchar();
> 		    scanf("%c%d",&v2,&weight);
> 			E[e].v1 = (int)(v1 - 'A');
> 			E[e].v2 = (int)(v2 - 'A');
> 			E[e].weight = weight;
> 			e++;
> 		}
> 		
> 	}
> 	return e;
> }
> 
> int main()
> {
> 	int n, e;
> 
> 	while(scanf("%d",&n)==1&&n)
> 	{
> 		e = get_graph(n);
> 		MSW = 0;
> 		qsort(E,e,sizeof(E[0]),cmp);
> 		kruskal(E,n,e);
> 		printf("%d\n",MSW);
> 	}
> 	return 1;
> }

• Re:Why RE?(内附代码) (8) zgw 2007-02-22 21:06:11