2149311_ac_107ms_232k.c

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

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

int n, m;
struct node
{
	int st;
	int ed;
	long w;
}E[15001];

struct Node
{
	int st;
	int ed;
}output[1000];

int cmp(const void *a,const void *b)
{
	struct node *aa = (struct node *)a;
	struct node *bb = (struct node *)b;
	return aa->w-bb->w;
}

void kruskal()
{
	int i, j, k;
	int vest[1001];
	int sn1, sn2;
	long max;
	
	for(i = 0; i < n; i++)
		vest[i] = i;
	j = 0;k = 1;max = -1;
	while(k < n)
	{
		sn1 = vest[E[j].st]; sn2 = vest[E[j].ed];
	    if(sn1!=sn2)
		{
			output[k-1].ed = E[j].ed;output[k-1].st = E[j].st;
			k++;
			if(E[j].w>max)
				max = E[j].w;
	   	    for(i = 0; i < n; i++)
				if(vest[i]==sn2)
					vest[i] = sn1;
		}
		j++;
	}
	printf("%ld\n%d\n",max,n-1);
	for(i = 0; i < n - 1; i++)
		printf("%d %d\n",output[i].st+1,output[i].ed+1);
}

void input()
{
	int i, st, ed;

	scanf("%d%d",&n,&m);
	for(i = 0; i < m; i++)
	{
		scanf("%d%d%d",&st,&ed,&E[i].w);
		E[i].ed = ed-1;E[i].st = st-1;
	}
	qsort(E,m,sizeof(E[0]),cmp);
	kruskal();
}

int main()
{
	input();
	return 1;
}