布线优化解决方案研究报告
最优布线问题
题目描述
学校有n台计算机,为了方便数据传输,现要将它们用数据线连接起来。两台计算机被连接是指它们间有数据线连接。由于计算机所处的位置不同,因此不同的两台计算机的连接费用往往是不同的。
当然,如果将任意两台计算机都用数据线连接,费用将是相当庞大的。为了节省费用,我们采用数据的间接传输手段,即一台计算机可以间接的通过若干台计算机(作为中转)来实现与另一台计算机的连接。
现在由你负责连接这些计算机,任务是使任意两台计算机都连通(不管是直接的或间接的)。
输入
输入文件wire.in,第一行为整数n(2<=n<=100),表示计算机的数目。此后的n行,每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。
输出
输出文件wire.out,一个整数,表示最小的连接费用。
样例输入
3
0 1 2
1 0 1
2 1 0
样例输出
2
1)、解题思路:
Prim算法:任取一个顶点加入生成树,然后对那些顶点在生成树中而另一个顶点不在生成树中的边进行排序,将权值最小的边和她的另一端点加入生成树中,并用t记录费用,重复上述步骤,直至所有顶点都进入生成为止。、
(2)、代码详解:
var coast:array [1..100,1..100] of longint; //图的邻接矩阵
mincoast:array [1..100] of longint; //mincoast用来更新已加入顶点和未加入顶点的权值
min,n,k,j,s,t,i:longint; //t记录费用,n表示计算机数目
begin
readln(n); //输入
for i:=1 to n do
for j:=1 to n do
read(coast[i,j]); //读入矩阵
for i:=1 to n do
mincoast[i]:=coast[1,i]; //初始化矩阵
t:=0; //t用来记录连接费用
for i:=2 to n do //prim算法
begin
min:=maxint; //初始化min
for j:=1 to n do
if (mincoast[j]<min)and(mincoast[j]<>0)then //找出最小权值
begin
min:=mincoast[j];
k:=j; //记录最小值的点
end;
inc(t,mincoast[k]); //选取最小边,并将其顶点加入
mincoast[k]:=0;
for j:=1 to ndo
if(coast[k,j]<mincoast[j])and(mincoast[j]<>0)then
mincoast[j]:=coast[k,j]; //更新权值
end;
writeln(t); //输出
end.
(3)、心得体会:
这是一道最基础的最小生成树问题,以此来对prim进行巩固复习。
上一篇: 简易安装 SVN 与自动化更新教程
下一篇: 内网渗透-不出网渗透技巧
推荐阅读
-
电脑小贴士:优化边缘浏览器以占用 C 盘空间的解决方案
-
优化 [.NET] Log4net FileAppender 和 MinimalLock 性能问题的解决方案(第二部分:使用 MSMQ)
-
优化云端视频播放速度:云服务器加速解决方案
-
布线优化解决方案研究报告
-
简易版:使用PSOGWO(粒子群与灰狼优化算法结合)在Matlab中寻找最佳解决方案的实例代码
-
LeetCode问题300:找寻最长上升子序列 - 暴力递归方法(效率低至O(n^3))、动态规划优化(提升到O(n^2))、结合动态规划与二分查找的高效解决方案(达到O(nlogn))
-
车载音频/视频媒体播放器优化解决方案
-
前端优化解决方案 - 解决请求耗时问题
-
动画卡顿优化总结:卡顿原因分析与优化解决方案
-
这可能是最完整的 sql 优化解决方案了