1946366_re.c

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

/*----------------------------------*/
/*  kruskal算法的是复杂度为O(elne), */
/*  取决于边数，比较适合于稀疏图。  */
/*----------------------------------*/
# include <stdio.h>
# include <stdlib.h>

# define MAXV 50
# define MAXE 1000

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)
		{
			//printf("%d\n",E[j].weight);
			k++;
			MSW += E[j].weight;
			for(i = 0; i < n; i++)
				if(vest[i]==sn2)
					vest[i] = sn1;
		}
		j++;
	}
	printf("%d\n",MSW);
}

void get_graph(int n,int *e)
{
	int N, weight;
	char v1,  v2;

	n--;
	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)++;
		}
		
	}
}

int main()
{
	int n, e;

	while(scanf("%d",&n)==1&&n)
	{
		e = 0;
		get_graph(n,&e);
		MSW = 0;
		qsort(E,e,sizeof(E[0]),cmp);
		kruskal(E,n,e);
	}
	return 1;
}