7-10 公路村村通(30 分)(最小生成树Prim算法)


7-10公路村村通(30分)

现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。

输入格式:

输入数据包括城镇数目正整数N(1000)和候选道路数目M(3N);随后的M行对应M条道路,每行给出3个正整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从1到N编号。

输出格式:

输出村村通需要的最低成本。如果输入数据不足以保证畅通,则输出1,表示需要建设更多公路。

输入样例:

6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

输出样例:

12

解题思路:1、这道题一开始走偏了想直接同floyd算法求出最短路径然后相加了

最小生成树能够保证整个拓扑图的所有路径之和最小,但不能保证任意两点之间是最短路径。
最短路径是从一点出发,到达目的地的路径最小。

2、理清楚了最小生成树与最短路径之间的区别以后就很容易想到用最小生成树算法了,这里选用的是Prim算法

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 #define MAXVEX 1003
 5 #define INFINITY  65535
 6 
 7 void CreateGraph( );
 8 int  Prim();
 9 
10 int G[MAXVEX][MAXVEX],Nv,Ne;
11 
12 int main()
13 {
14     int f = 0;
15 
16     scanf("%d %d",&Nv,&Ne);
17     CreateGraph();
18     f =Prim();
19     printf("%d",f);
20 
21     return 0;
22 }
23 
24 void CreateGraph()
25 {
26     //用邻接矩阵表示图
27     int i,j;
28     int v1,v2,w;
29 
30     for( i=1; i<=Nv; i++)
31     {
32         for( j=1; j<=Nv; j++)
33         {
34             G[i][j] = INFINITY;  //初始化
35         }
36     }
37 
38     for( i=0; i<Ne; i++)  //注意这里是读入边
39     {
40         scanf("%d %d %d",&v1,&v2,&w);
41         G[v1][v2] = w;         //读入权值
42         G[v2][v1]= G[v1][v2];  //无向图对称
43     }
44 }
45 
46 
47 int  Prim()
48 {
49     int min;
50     int i,j,k;
51     int lowcost[MAXVEX];
52     int cost =0;
53 
54 
55     lowcost[1] = 0;   //初始化第一个权值为0,即v0加入生成树
56 
57     for( i=2; i<=Nv; i++)
58     {
59         lowcost[i] = G[1][i];
60     }
61 
62     for( i=2; i<=Nv; i++)
63     {
64         min = INFINITY;
65         j = 1;
66         k = 0;
67         while( j<=Nv )
68         {
69             if( lowcost[j]!=0 && lowcost[j]<min)
70             {
71                 min = lowcost[j];
72                 k = j;   //将当前最小值的下标存入k
73             }
74             j++;
75         }
76 
77         if(k==0)
78         {
79             return -1;  //不连通
80         }
81         cost += min;
82         lowcost[k] = 0;   //将当前顶点设置为0,表示此结点已经完成任务
83 
84         for( j=2; j<=Nv; j++)
85         {
86             if( lowcost[j]!=0 && G[k][j]<lowcost[j])
87             {
88                 //若下标为k顶点各边权值小于此前这些顶点未被加入生成树的权值
89                 lowcost[j] = G[k][j];
90             }
91         }
92 
93     }
94 
95     return cost;
96 }

优质内容筛选与推荐>>
1、asp.net读取二进制图片
2、/bin目录文件内容:二进制可执行命令文件所在
3、JS--该死的&&和||
4、Redis-发布与订阅
5、C#==>匿名方法 【转】


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号





    联系我们

    欢迎来到TinyMind。

    关于TinyMind的内容或商务合作、网站建议,举报不良信息等均可联系我们。

    TinyMind客服邮箱:support@tinymind.net.cn