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

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

注意：

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

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

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

#include 
     
      #include 
      
       const int MAX_VEC = 101;int N;	//number of verticesstruct 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;}