图结构练习——最小生成树（prim算法(普里姆)）-白红宇

图结构练习——最小生成树（prim算法(普里姆)）

阅读量：426 次

发布时间：2019-03-06

本文共 1569 字，大约阅读时间需要 5 分钟。

图结构练习——最小生成树

Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^

题目描述

有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，使在任意一城市出发，可以到达其他任意的城市。

输入

输入包含多组数据，格式如下。

第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n<=100)

剩下m行每行3个正整数a b c，代表城市a 和城市b之间可以修建一条公路，代价为c。

输出

每组输出占一行，仅输出最小花费。

示例输入

3 21 2 11 3 11 0

示例输出

20 prim代码：

1 #include
        
          2 #include
         
           3 #include
          
            4 int map[101][101]; 5 int m,n; 6 int prim() 7 { 8     int lowcost[101]; 9     int f[101]={0};10     int  g[100];11     int i,j,min,k,sum=0;12     lowcost[1]=0;13     f[1]=1;14     g[0]=0;15     for(i=2;i<=m;i++)16       {17           lowcost[i]=map[1][i];18           g[i]=1;//本语句不可以省略19       }20     for(i=2;i<=m;i++)21     {22         min=65535;23         for(j=1;j<=m;j++)24             if(lowcost[j]<=min&&f[j]==0)//寻找与已经生成的最小生成树邻接的边的最小权值25             {26                 min=lowcost[j];//min是最小权值27                 k=j;//k是最小权值边的终端所对应的数组元素的下标28             }29         printf("%d->%d:%d\n",g[k],k,min);//本语句只是为表现出最小生成树的结构，g数组也是为此而定义，可省略该数组30         sum=sum+min;31         f[k]=1;//表明f[k]元素已经用完，下次再碰到时直接跳过32         for(j=1;j<=m;j++)//最重要的一步，不解释33         {34             if(map[k][j]
           
            w)//防止出现输入2 3 3，2 3 4这样的情况，所以要比较求出最小权值57              {58                  map[u][v]=w;59                  map[v][u]=w;60              }61          }62           sum=prim();63          printf("%d\n",sum);64     }65 }

View Code

示例：

输入：

6 10

1 2 6

2 5 3

5 6 6

6 4 2

4 1 5

3 1 1

3 2 5

3 5 6

3 6 4

3 4 5

输出：

转载地址：http://gedyz.baihongyu.com/

你可能感兴趣的文章