描述
为了促进山区乡镇的发展，*决定在山区修建道路。由于在山区修路的成本极高，因此修建道路总长越短越好，但是必须保证任意两个乡镇互相通达。
输入
输入：输入有多组，每组的第一行是一个整数N（3<=N<=100），表示乡镇总数。接下来有N行输入，每行N个数，每i行的第j个数表示村庄i和j的距离（距离在[1,1000]区间内）。
输出
对于每组数据，输出需要修建的最短道路长度。
样例输入
3
0 990 692
990 0 179
692 179 0
样例输出1
871
Prim算法：通俗的讲就是任意选一点，从这点开始每次选择距离已生成树的距离最小的一点，直到所有的点都经过。
int graph[150][150];
int dist[150];
int mst[150];
int prim(int graph[][150],int n){
int i,j,minid=0,sum=0;
for(i=2;i<=n;i++){
dist[i]=graph[1][i];
mst[i]=1;
}
mst[1]=0;
dist[1]=0;
for(i=2;i<=n;i++){
int mmin=99999;
for(j=2;j<=n;j++){
if(dist[j]<mmin&&dist[j]){ //找一条到树距离最短的并且没走过的路
mmin=dist[j];
minid=j;
}
}
sum+=mmin;
dist[minid]=0;
for(j=2;j<=n;j++){
if(dist[j]>graph[minid][j]){ //更新未经过的点到已生成树的距离
dist[j]=graph[minid][j];
mst[j]=minid;
}
}
}
return sum;
}
int main(){
int n;
while(cin>>n){
memset(graph,0,sizeof(graph));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>graph[i][j];
cout<<prim(graph,n)<<endl;
}
return 0;
}Kruscal算法：通俗的讲就是将边按照从小到大的顺序排序，按从小到大的顺序每次判断边的两点是否联通，若不联通就将其联通，并将这条路加到计算结果里。
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int father[105];
int graphh[105][105];
struct Road{
int anode,bnode;
int value;
};
bool cmp(Road a,Road b){
return a.value<b.value;
}
int findd(int x){ //并查集
if(father[x]!=x)
x=findd(father[x]);
return x;
}
int main(){
int n,i,j;
Road roadd[10500]; //这个数组要按照 n*n/2 的大小开
while(cin>>n){
memset(roadd,0,sizeof(roadd));
memset(graphh,0,sizeof(graphh));
int k=1; //因为并查集的数组是从1号位置（非0号位置）开始的，所以为了方便roadd也要从1开始，因此这里设置k=1
for(i=1;i<=n;i++)
father[i]=i;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
cin>>graphh[i][j];
if(j>i){
roadd[k].anode=i;
roadd[k].bnode=j;
roadd[k].value=graphh[i][j];
k++; //控制存roadd的位置
}
}
sort(roadd+1,roadd+k,cmp);
int cnt=0,ans=0;
for(i=1;i<=k;i++){
if(cnt>n-1) break;
if(findd(roadd[i].anode)!=findd(roadd[i].bnode)){
ans+=roadd[i].value;
father[findd(roadd[i].anode)]=findd(roadd[i].bnode); //这里一定是合并根节点！如果不合并根节点的话会出现已经生成的树被割断的情况，比如：father[1]==1,father[2]==1,father[3]==4,father[4]==4，如果现在要联通2和3的话，如果不合并根节点就会有father[2]==3，那么1和2就不连接了。
}
}
cout<<ans<<endl;
}
return 0;
}