HDOJ 1301 Jungle Roads

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1301

//HDOJ1301
#include<iostream>#include<cstring>
using namespace std;
#define MAX 99999
#define LEN 30
int dist[LEN];//某点的权值  起始点到目标点的权值
int map[LEN][LEN];//某点到某点两点之间的权值
bool isvisitd[LEN];//表示某点是否访问过

//初始化map数组  设置为无穷大
void  init(int n){
    for(int  i = 0;i<=n;i++) {
         for(int  j = 0;j<=n;j++)
            map[i][j] = MAX;
     }
} 

//prim最小生成树的算法
int prim(int n){
    int i,j,min,pos,sum;
    sum = 0;   //最小生成树的权值

    //初始化，表示没有一点走过
    memset(isvisitd,false,sizeof(isvisitd));

    //初始化给dist数组赋值
    for(i = 1;i<=n;i++){
        dist[i] = map[1][i];
    }

    isvisitd[1] = true;//标记1已被访问  从1开始

    //找到权值最小点并记下位置
    for(i = 1;i<n;i++){
            min = MAX;
            for(j = 1;j<=n;j++){
            if(!isvisitd[j]&&dist[j]<min){
                min = dist[j];
                pos = j;//记录下该位置
            }
        }

        sum+=min;
        isvisitd[pos] = true;

        //更新权值
        for(j = 1;j<=n;j++)    {
            if(!isvisitd[j]&&dist[j]>map[pos][j]){
                dist[j] = map[pos][j];
            }
        }

    }
    return sum;
}
int main(){
    int i,j,n,m,len;
    char start,end;
    while(scanf("%d",&n)!=EOF){
        if(n==0){
            break;
        }

        init(n);//初始化

        for(i=0;i<n-1;i++){
            cin>>start>>m;
            for( j = 0;j<m;j++){
                cin>>end>>len;
                map[i+1][end-'A'+1] = len;
                map[end-'A'+1][i+1] = len;
            }
        }
        cout<<prim(n)<<endl;
    }
    return 0;

}

运行结果如下：

最小生成树 Prim算法的实现及应用  http://blog.csdn.net/worker90/article/details/6642959