http://poj.org/problem?id=1258
这道题是最简单的一个啦,,,,
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=;
#define M 0x3f3f3f3f///设置无穷大的数M,当两点之间无法联通时设两者之间距离为M
int ma[N][N],low[N],vis[N];///ma记录道路的长度,low记录最短的路径,vis判断是否经过这点
int n;
int prim(){
int i,j,pos,mi,result=;
memset(vis,,sizeof(vis));
vis[]=;///从1开始遍历
pos=;///记录当前结点 for(i=;i<=n;i++)
if(i!=pos)low[i]=ma[pos][i];///,初始时pos等于1,查找pos周围可以通过的结点中最短的距离并存储在low中 for(i=;i<n;i++){///遍历n-1次
mi=M;
for(j=;j<=n;j++){
if(vis[j]==&&mi>low[j]){
mi=low[j];
pos=j; }
}
result+=mi;
vis[pos]=;
for(j=;j<=n;j++){///查找pos周围的最短的距离
if(vis[j]==&&low[j]>ma[pos][j])
low[j]=ma[pos][j];
}
}
return result;
}
int main()
{
int i,v,j,ans;
while(~scanf("%d",&n)){
memset(ma,M,sizeof(ma));
for(i=;i<=n;i++){
for(j=;j<=n;j++){
scanf("%d",&v);
ma[i][j]=ma[j][i]=v; }
}
ans=prim();
cout<<ans<<endl;
}
return ;
}