学步园

在一张图上有N个点，点与点之间的连接的花费都已经告诉你了，请你设计一下，如果解决这个“最小生成树”的问题。

输入
首先输入一个数字N（0〈=N〈=100）
然后输入一个N*N的矩阵 其中第i行第j列的数字k表示从点i到点j需要的花费。

输出
一个数字，最少需要多少花费才能使得整张图任意两点都直接或者间接连通（也就是最小生成树的权）

Sample Input
5
0 41 67 34 0 
41 0 69 24 78 
67 69 0 58 62 
34 24 58 0 64 
0 78 62 64 0

0

2
0 1
1 0

Sample Output
116
0
1

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 101

struct stuEdg{
	int nFrom ;
	int nTo;
	int nCost;
};

int nInput(stuEdg stuEdgs[],int nNodes);
void vSort(stuEdg stuEdgs[],int nExistEdgs);
bool bCmp(stuEdg stuEdg1,stuEdg stuEdg2);
void vInit(int nArry[],int nNodes);
int nKru(stuEdg stuEdgs[],int nArry[],int nNodes);
void vOutput(int nMin);
void vSetMerge(int nArry[],int nA,int nB,int nNodes);

int main(){
	stuEdg stuEdgs[MAX*(MAX-1)/2+1];
	int nNodes;
	int nExistEdgs;
	int nMin;
	int nArry[MAX+1];
	while(1==scanf("%d",&nNodes)){
		nExistEdgs=nInput(stuEdgs,nNodes);
		vInit(nArry,nNodes);
		vSort(stuEdgs,nExistEdgs);
		nMin=nKru(stuEdgs,nArry,nNodes);
		vOutput(nMin);
	}
	return 0;
}

int nInput(stuEdg stuEdgs[],int nNodes){
	int i;
	int j;
	int nTemp;
	int nEdgCount=0;
	for(i=1;i<=nNodes;i++){
		for(j=1;j<=nNodes;j++){
			scanf("%d",&nTemp);
			if(i<j){
				nEdgCount++;
				stuEdgs[nEdgCount].nCost=nTemp;
				stuEdgs[nEdgCount].nFrom=i;
				stuEdgs[nEdgCount].nTo=j;
			}
		}
	}
	return nEdgCount;
}

void vInit(int nArry[],int nNodes){
	int i;
	for(i=1;i<=nNodes;i++){
		nArry[i]=i;
	}
}

bool bCmp(stuEdg stuEdg1,stuEdg stuEdg2){
	return stuEdg1.nCost<stuEdg2.nCost;
}
void vSort(stuEdg stuEdgs[],int nExistEdgs){
	sort(stuEdgs+1,stuEdgs+nExistEdgs+1,bCmp);
}

int nKru(stuEdg stuEdgs[],int nArry[],int nNodes){
	int nEdgMark;
	int nMin;
	int nA;
	int nB;
	int nN;
	nN=nNodes;
	nEdgMark=1;
	nMin=0;
	while(nNodes>1){
		nA=nArry[stuEdgs[nEdgMark].nFrom];
		nB=nArry[stuEdgs[nEdgMark].nTo];
		if(nA!=nB){
			nMin+=stuEdgs[nEdgMark].nCost;
			vSetMerge(nArry,nA,nB,nN);
			nNodes--;
		}
		nEdgMark++;
	}
	return nMin;
}

void vSetMerge(int nArry[],int nA,int nB,int nNodes){
	int i;
	for(i=1;i<=nNodes;i++){
		if(nArry[i]==nB){
			nArry[i]=nA;
		}
	}
}

void vOutput(int nMin){
	printf("%d\n",nMin);
}