BZOJ1083 [SCOI2005]繁忙的都市（最小生成樹）

【題解】

裸的Kruskal，将邊從小到大排序，依次加邊，并查集維護連通性即可

#include<stdio.h>
#include<stdlib.h>
int fa[305]={0},u[90005]={0},v[90005]={0},w[90005]={0};
int father(int x)
{
	if(fa[x]!=x) fa[x]=father(fa[x]);
	return fa[x];
}
void jh(int* a,int* b)
{
	int t=*a;
	*a=*b;
	*b=t;
}
void kp(int low,int high)
{
	int i=low,j=high,mid=w[(i+j)/2];
	while(i<j)
	{
		while(w[i]<mid) i++;
		while(w[j]>mid) j--;
		if(i<=j)
		{
			jh(&u[i],&u[j]);
			jh(&v[i],&v[j]);
			jh(&w[i],&w[j]);
			i++;
			j--;
		}
	}
	if(j>low) kp(low,j);
	if(i<high) kp(i,high);
}
int main()
{
	int n,m,i,num=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
		scanf("%d%d%d",&u[i],&v[i],&w[i]);
	kp(1,m);
	for(i=1;i<=n;i++)
		fa[i]=i;
	for(i=1;i<=m;i++)
	{
		if(father(u[i])!=father(v[i]))
		{
			fa[father(u[i])]=father(v[i]);
			num++;
		}
		if(num==n-1) break;
	}
	printf("%d %d",n-1,w[i]);
	return 0;
}