2563854_re.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 72 行

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

# define MAXV 1011
# define MAXE 20010

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

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

void kruskal(int n)
{
	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)
	{
		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 main()
{
	int i;
	int n, e;
	int a, b, c;


	scanf("%d%d",&n,&e);
	for(i = 0; i < e; i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		a--,b--;
		E[i].v1 = a,E[i].v2 = b;
		E[i].weight = c;
	}
	MSW = 0;
	qsort(E,e,sizeof(E[0]),cmp);
	kruskal(n);
	printf("%d\n",MSW);
	return 1;
}