搭建一个最小代价的网络，最原始的最小生成树的应用。

这里使用Union find和Kruskal算法求解.

注意：

1 给出的数据是原始的矩阵图，可是须要转化为边表示的图，方便运用Kruskal，由于须要sort

2 降低边。一个矩阵最多须要(N*N-N)>>1条边，有人讨论本题是否有向，那是无意义的。由于本题的最小生成树和方向无关。

3 使用Union find是为了推断是否有环。比原始推断快非常多。

#include <stdio.h>

#include <stdlib.h>

const int MAX_VEC = 101;

int N;	//number of vertices

struct SubSet

{

	int p, rank;

};

struct Edge

{

	int src, des, wei;

};

struct Graph

{

	int V, E;

	Edge *edge;

	Graph(int v, int e) : V(v), E(e)

	{

		edge = new Edge[E];

	}

	~Graph()

	{

		if (edge) delete[]edge; edge = NULL;

	}

};

static int cmp(const void *a, const void *b)

{

	Edge *a1 = (Edge *) a;

	Edge *b1 = (Edge *) b;

	return a1->wei - b1->wei;

}

SubSet *subs;

Edge *res;

Graph *gra;

void initResource()

{

	subs = new SubSet[N];

	for (int i = 0; i < N; i++)

	{

		subs[i].p = i;

		subs[i].rank = 0;

	}

	res = new Edge[N-1];

}

inline void releaseResource()

{

	if (subs) delete [] subs;

	if (res) delete [] res;

}

int find(int node)

{

	if (subs[node].p != node)

		subs[node].p = find(subs[node].p);

	return subs[node].p;

}

inline void unionTwo(int x, int y)

{

	int xroot = find(x);

	int yroot = find(y);

	if (subs[xroot].rank < subs[yroot].rank) subs[xroot].p = yroot;

	else if (subs[xroot].rank > subs[yroot].rank) subs[yroot].p = xroot;

	else

	{

		subs[xroot].rank++;

		subs[yroot].p = xroot;

	}

}

int mst()

{

	initResource();

	qsort(gra->edge, gra->E, sizeof(Edge), cmp);

	for (int i = 0, v = 0; i < gra->E && v < gra->V - 1; i++)

	{

		int xroot = find(gra->edge[i].src);

		int yroot = find(gra->edge[i].des);

		if (xroot != yroot)

		{

			unionTwo(xroot, yroot);

			res[v++] = gra->edge[i];

		}

	}

	int ans = 0;

	for (int i = 0; i < N-1; i++)

	{

		ans += res[i].wei;

	}

	releaseResource();

	return ans;

}

int main()

{

	int w;

	while (~scanf("%d", &N))

	{

		gra = new Graph(N, (N*N-N)>>1);

		int e = 0;

		for (int i = 0; i < N; i++)

		{

			for (int j = 0; j < N; j++)

			{

				scanf("%d", &w);

				if (j <= i) continue;		//下三角形的值不入边

				gra->edge[e].src = i;

				gra->edge[e].des = j;

				gra->edge[e++].wei = w;

			}

		}

		printf("%d\n", mst());

		delete gra;

	}

	return 0;

}