学步园

题意：将n个小镇连接起来，求最小生成树。
题解：

#include <iostream>
using namespace std;

int t,n,father[501];

struct path
{
	int u,v,w;
} edge[501 * 500 / 2];

int cmp(const void *a, const void *b)
{
	return (*(path *)a).w - (*(path *)b).w;
}

int find_set ( int x )
{
	if ( x != father[x] )
		father[x] = find_set ( father[x] );
	return father[x];
}

int Kruskal ( int x )
{
	int i, ans = 0;
	for ( i = 0; i < n; i++ )
		father[i] = i;

	qsort ( edge, x, sizeof(path), cmp );

	for ( i = 0; i < x; i++ )
	{
		int a = find_set(edge[i].u);
		int b = find_set(edge[i].v);
		if ( a != b )
		{
			father[b] = a;
			ans = edge[i].w;
		}
	}
	return ans;
}

int main()
{
	cin >> t;
	while ( t-- )
	{
		cin >> n;
		int c = 0, distance;
		memset(edge,0,sizeof(edge));
		for ( int i = 0; i < n; i++ )
		{
			for ( int j = 0; j < n; j++ )
			{
				cin >> distance;
				if ( i < j )
				{
					edge[c].u = i;
					edge[c].v = j;
					edge[c].w = distance;
					c++;
				}
			}
		}
		cout << Kruskal(c) << "\n";
	}
	return 0;
}