Pro.ID2082 TitleAL087 布线问题 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=2082 AC0 Submit1 Ratio0.00% 时间&空间限制描述假设要将一组元件安装在一块线路板上,为此需要设计一个线路板布线方案。各元件的连线数由连线矩阵conn给出。元件i和元件j之间的连线数为conn(i,j)。如果将元件i安装在线路板上位置r处,而将元件j安装在线路板上位置s处,则元件i和元件j之间的距离为dist(r,s)。确定了所给的n 个元件的安装位置,就确定了一个布线方案。与此布线方案相应的布线成本为 。 对于给定的n个元件,设计一个优先队列式分支限界法,计算最佳布线方案,使布线费用达到最小。 输入输入第一行有一个正整数n( 1 ≤ n ≤ 20 )。接下来的n-1行,每行n-i个数,表示元件i和元件j之间连线数,1 ≤ i < j ≤ 20。 输出Description 假设要将一组元件安装在一块线路板上,为此需要设计一个线路板布线方案。各元件的连线数由连线矩阵conn给出。元件i和元件j之间的连线数为conn(i,j)。如果将元件i安装在线路板上位置r处,而将元件j安装在线路板上位置s处,则元件i和元件j之间的距离为dist(r,s)。确定了所给的n 个元件的安装位置,就确定了一个布线方案。与此布线方案相应的布线成本为 。 对于给定的n个元件,设计一个优先队列式分支限界法,计算最佳布线方案,使布线费用达到最小。 Input 输入第一行有一个正整数n( 1 ≤ n ≤ 20 )。接下来的n-1行,每行n-i个数,表示元件i和元件j之间连线数,1 ≤ i < j ≤ 20。 Output 输出最小布线费用以及相应的最佳布线方案 Sample Input 3 Sample Output 10 Author 样例输入3 样例输出10 提示作者 |