描述
有电线需要改造,现在要求设计师设计出一种布线方式,该布线方式需要满足以下条件:
1、把所有的楼都供上电。
2、所用电线花费最少
输入
第一行是一个整数n表示有n组测试数据。(n<5)
每组测试数据的第一行是两个整数v,e.
v表示学校里楼的总个数(v<=500)
随后的e行里,每行有三个整数a,b,c表示a与b之间如果建铺设线路花费为c(c<=100)。(哪两栋楼间如果没有指明花费,则表示这两栋楼直接连通需要费用太大或者不可能连通)
随后的1行里,有v个整数,其中第i个数表示从第i号楼接线到外界供电设施所需要的费用。( 0<e<v*(v-1)/2 )(楼的编号从1开始),由于安全问题,只能选择一个楼连接到外界供电设备。
数据保证至少存在一种方案满足要求。
输出
每组测试数据输出一个正整数,表示铺设满足校长要求的线路的最小花费。
样例输入
1
4 6
1 2 10
2 3 10
3 1 10
1 4 1
2 4 1
3 4 1
1 3 5 6
样例输出
4
思路:
最小生成树的prime算法。
1.将第一个点放入最小生成树的集合中(标记visit[i]=1意思就是最小生成树集合)。
2.从第二个点开始,初始化lowcost[i]为跟1点相连(仅仅相连)的边的权值(lowcost[i]不是这个点的最小权值!在以后会逐步更新)。
3.找最小权值的边。
从第二点开始遍历,如果不是最小生成树的集合的点,则找出从2到n的最小权值(lowcost[j])。
4.将找出来的最小权值的边的顶点加入最小生成树的集合中(标记visit[i] = 1),权值想加。
5.更新lowcost[j]集合。
假设第一次:lowcost[2]代表与1相连的点的权值,现在加入了k点。则比较k点与2点的边map[k][2]和lowcost[2]的大小,若lowcost[2]大,则lowcost[2] = map[k][2]。(关键步骤:实质就是每在最小生成树集合中加入一个点就需要把这个点与集合外的点比较,不断的寻找两个集合之间最小的边)
6.循环上述步骤,指导将全部顶点加入到最小生成树集合为止。
代码如下:
克鲁斯卡尔算法也可以。算法如下:
函数写法:
仅仅因为father[root1] = root2这个错误找了一个上午,看来变量的名字一定要慎重的选择。特别具有迷惑性。。。。。
分享到:
相关推荐
算法分析与设计电路布线问题算法分析与设计电路布线问题算法分析与设计电路布线问题算法分析与设计电路布线问题算法分析与设计电路布线问题算法分析与设计电路布线问题
分支限界法 实现布线问题 java中的Swing实现,带有详细的算法说明和图像展示···
利用队列解决布线问题的C++代码 利用队列解决布线问题的C++代码
印刷电路板最短布线问题 一般解空间树的求解问题 java实现
本文详细介绍了 电路布线问题的详细方法,有详细的源程序代码
本例采用队列式分支限界法解决布线问题,参考:算法设计与分析
布线问题,和迷宫问题是同一类问题。都是通过广度优先搜索来解决的。当然,深度就更好了。
用JAVA实现的布线问题求解,用JAVA实现的布线问题求解
布线问题 分支限界算法 java算法分析
算法分析里的布线问题实现,支持100*100范围内的布线问题,可以自己设置布线中的障碍位置。
实验要求:请在下图所给出电路板中,按布线要求,利用队列式或优先队列分支限界法实现从a到b的布线工作
java算法分析与设计之电路布线问题源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络资源少的可怜,...
通过动态规划的思想解决电路布线问题。 主要分为两个部分:1.求size[i][j]. 2.根据求得的size[i][j]导出最大不相交连线集。
开关盒布线问题 开关盒布线问题:给定一个矩形布线区域,其外围有若干针脚。两个针脚之间通过布设一条金属线路而实现互连。这条线路被称为电线,被限制在矩形区域内。如果两条电线发生交叉,则会发生电流短路。所以...
采用c++语言对布线问题进行描述,采用分支限界的方法。采用优先式队列。
vs2010开发的WINFORM程序,有UI界面,可以添加特殊点和起始位置,路径有着色
给定一个矩形布线区域,其外围有若干针脚。两个针脚之间通过布设一条金属线路而实现互连。这条线路被称为电线,被限制在矩形区域内。如果两条电线发生交叉,则会发生电流短路。所以,不允许电线间的交叉。每对互连的...
费了好大的劲才搞定,应用分支界限法!
不仅能搜索出最短路径长,还能输出具体路径
本文主要从实践的角度来探讨高速电路的布线问题,主要目的在于帮助新用户当进行设计高速电路PCB布线时,能注意到需要考虑的多种不同问题。另一个目的是为已经有一段时间没接触PCB布线的客户提供一种复习数据。受限于...