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

struct line1
{
	int x;
	int y;
	long len;
}line[15001];

struct node
{
	int root;
	int parent;
}node[1001];

int m, n, used[1001];

int cmp(const void *a,const void *b)
{
	return (*(struct line1 *)a).len>(*(struct line1 *)b).len?1:-1;
}

int find (int e)
{
	int current=e,p,gp;
	if(node[current].root)return current;
	p=node[current].parent;
	if(node[p].root)return p;
	gp=node[p].parent;
	while(1)
	{
		node[current].parent=gp;
		if(node[gp].root) return gp;
		current=p;
		p=gp;
		gp=node[p].parent;
	}
}

void u(int i,int j)
{
	if(i==j)return;
	if(node[i].parent<node[j].parent)
	{
		node[j].parent+=node[i].parent;
		node[i].root=0;
		node[i].parent=j;
	}
	else
	{
		node[i].parent+=node[j].parent;
		node[j].root=0;
		node[j].parent=i;
	}
}

void preset()
{
	int i;
	for(i=0;i<=n;i++)
	{
		node[i].parent=1;
		node[i].root=1;
	}
}

long Kruskal()
{
	long max = 0;
	int fa, fb, i, j = 0;
	preset();

	for(i = 0; i < m; i++) {
		fa = find(line[i].x);
		fb = find(line[i].y);
		if(fa != fb) {
			if( max < line[i].len)max = line[i].len;
			u(fa, fb);
			used[j++] = i;
			if(j >= n-1)break;
		}
	}
	return max;
}

int main()
{
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++)
		scanf("%d%d%ld",&line[i].x,&line[i].y,&line[i].len);
	qsort(line, m, sizeof(line[0]), cmp);
	printf("%ld\n%d\n",Kruskal(),n-1);
	for(i=0;i<n-1;i++)
		printf("%d %d\n",line[used[i]].x,line[used[i]].y);
	return 0;
}

• Re:怎么用kruskal这么慢,966ms?? (1635) 546711990 2009-07-14 15:14:19