题目描述
假设要将一组元件安装在一块线路板上,为此需要设计一个线路板布线方案。各元件的连线数由连线矩阵conn给出。元件i和元件j之间的连线数为conn(i,j)。如果将元件i安装在线路板上位置r 处,而将元件j 安装在线路板上位置s 处,则元件i 和元件j 之间的距离为dist(r,s)。确定了所给的n 个元件的安装位置,就确定了一个布线方案。与此布线方案相应的布线成本为:
。
试设计一个算法找出所给n个元件的布线成本最小的布线方案。
设计一个算法,对于给定的n个元件,计算最佳布线方案,使布线费用达到最小。
输入
输入数据的第一行有1 个正整数n (1≤n≤20)。接下来的n-1 行,每行n-i个数,表示元件i和元件j之间连线数,1≤iOutput将计算出的最小布线费用以及相应的最佳布线方案输出。Sample Input
.wrapper {position: relative;}
#input {position: absolute;top: 0;left: 0;opacity: 0;z-index: -10;}
function copyText() {
var text = document.getElementById("test").innerText;
var input = document.getElementById("input");
input.value = text; // 修改文本框的内容
input.select(); // 选中文本
document.execCommand("copy"); // 执行浏览器复制命令
//alert("复制成功");
}
copy
3
2 3
3
Made by hxl.
Sample Output
10
1 3 2Source [Submit][Status]
输出
将计算出的最小布线费用以及相应的最佳布线方案输出。
样例输入
3
2 3
3
样例输出
10
1 3 2
参考代码
暂无
解析
暂无