随笔-65  评论-6  文章-0  trackbacks-0
 1 /*
 2 Author:    Leo.W
 3 Descriptipn:    给定几个顶点以及各顶点间的距离,求连接所有顶点的所需的最短距离。
 4 How to Do:    基础的最小生成树问题。易知此为稠密图,故使用普里姆算法解题。
 5   */
 6 #include <iostream>
 7 #include <stdio.h>
 8 #include <string.h>
 9 using namespace std;
10 
11 #define MAXSIZE 100
12 int closePath[MAXSIZE];
13 int path[MAXSIZE][MAXSIZE];
14 bool chose[MAXSIZE];
15 int n;//顶点数
16 
17 int prim(int a){
18     chose[a]=true;
19     int i,sum=0,num=n-1,pos=a;
20     for(i=1;i<=n;i++)    closePath[i]=path[a][i];
21     while(num){
22         int mins=10000000;
23         for(i=1;i<=n;i++){
24             if(!chose[i]&&closePath[i]<mins){
25                 mins=closePath[i];
26                 pos=i;
27             }
28         }
29         num--;    sum+=mins;
30         chose[pos]=true;
31         for(i=1;i<=n;i++){
32             if(!chose[i]&&closePath[i]>path[pos][i]){
33                 closePath[i]=path[pos][i];
34             }
35         }
36     }
37     return sum;
38 }
39 int main(){
40     //freopen("in.txt","r",stdin); 
41     while(scanf("%d",&n),n){
42         if(n==1)    printf("0\n");
43         else{
44             memset(chose,false,MAXSIZE);
45             int i,j,pathSum=n*(n-1)/2;
46             for(i=1;i<=n;i++){
47                 for(j=1;j<=n;j++){
48                     if(i==j)    path[i][j]=0;
49                     else    path[i][j]=10000000;
50                 }
51             }
52             for(i=1;i<=pathSum;i++){
53                 int begin,end,len;
54                 scanf("%d%d%d",&begin,&end,&len);
55                 if(len<path[begin][end])
56                     path[begin][end]=path[end][begin]=len;
57             }
58             printf("%d\n",prim(1));
59         }    
60     }
61     return 0; 
62 } 
posted on 2012-03-05 18:30 Leo.W 阅读(157) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理