Preparing NOJ

排列树问题

1000ms 65536K

Description:

 试设计一个用队列式分支限界法搜索排列空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数,并将此函数用于解电路板排列问题。电路板排列问题是大规模电子系统设计中提出的实际问题。该问题的提法是,将n 块电路板以最佳排列方案插入带有n 个插槽的机箱中。n块电路板的不同的排列方式对应于不同

的电路板插入方案。

B={12,…,n }n 块电路板的集合。集合L={ N 1 N 2 ,…, N m }n 块电路板的m 个连接块。其中每个连接块N i B 的一个子集,且N i 中的电路板用同一根导线连接在一起。在设计机箱时,插槽一侧的布线间隙由电路板排列的密度所确定。因此电路板排列

问题要求对于给定电路板连接条件(连接块),确定电路板的最佳排列,使其具有最小密度。

对于给定电路板连接条件,编程计算电路板的最佳排列,使其具有最小密度。

Input:

 1行是2 个正整数nm,表示有n块电路板和m个连接块。接下来的n行每行有m个数,第i行的第j个数a[i][j]=1 表示第i块电路板在第j个连接块中,否则第i块电路板不在第j个连接块中。

Output:

 程序运行结束时,将计算出的最小密度和电路板的最佳排列输出。第1行是最小密度;第2行是电路板的最佳排列。

Sample Input:

8 5
1 1 1 1 1
0 1 0 1 0
0 1 1 1 0
1 0 1 1 0
1 0 1 0 0
1 1 0 1 0
0 0 0 0 1
0 1 0 0 1

Sample Output:

4
2 3 4 5 1 6 7 8

Note:

 

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1326

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet