把输入抽象为三组数据:
S_i
:第 i
层的候选集合;pair_i
:第 i
层的无向配对表;trans_i
:第 i
层的跨层映射(到第 i+1
层),末层为恒等。接着做一层深度优先搜索(DFS / 回溯):
现有N个设备从左到右依次排列,编号从1到N。每个设备中有多个端口,每个端口号都有一个数字编号,编号从1到M且不重复。设备内部端口之间的连接叫内部连线,设备之间的端口连接叫外部连线,设备只能跟编号相邻的设备有外部连接。现在已经有连接好的一部分内部和外部连线了,需要寻找一个权重最大的最优连接线路,将这N个设备从左到右顺序连接起来。每条连接线路会在每个设备中选择2个端口,分别叫左端口和右端口,并将这些端口连接起来,设备1的左端口为起始端口,设备N的右端口为终止端口。
条件约束:
1.设备数量N满足:1<N<20
2.每个设备内部端口编号 M 满足:1<M<100
3.除起始和终止两个端口只能连接一条内部连线外,其他端口必须一边连接内部连线,另一边连接外部连线。
4.设备之间已经连接好的外部连线不能修改也不能增加新的。
5.设备内部已经连接好的内部连线不能修改,只能增加新的。
权重计算:
1)不同设备之间,左边设备权重级别高于右边,也就是说两条线路从左往右比较设备权重值,一旦某个设备权重值高于另一个,则整个线路权重一定高,无需再比较后面的设备。
2)设备权重值(优先级高代表权重值高):优先选择已经连接好的内部连线,再优先选择左右端口号之和较小的两个端口,再优先选择左端口号较小的。
下图是一个当前已经存在的设备端口连接图:
下图是寻找到的最优连接图,其中的虚线是要新增的内部连接线。
设备的个数N
设备1内部端口号列表
设备1内部内部连线列表,如果没有则显示0
设备1和设备2之间外部连线列表,如果没有则显示0
设备2内部端口号列表
设备2内部连线列表,如果没有则显示0
设备2和设备3之间外部连线列表,如果没有则显示0
...
设备N内部端口号列表
设备N内部内部连线列表
备注:内部和外部连线都使用“端口号-端口号”表示。
比如题目中示例图的输入如下
3
1 2 3 4 5 6 7 8 9 10
1-2 5-6
2-1 6-5
1 2 3 4 5 6 7 8 9 10
0
6-1 8-3 10-5
1 2 3 4 5 6
3-2
输出从设备1到设备N连接起来的端口号列表。
题目中示例图的输出如下: 1 2 1 6 1 4
如果找不见一条连接光路,则输出−1
输入
15
1 2 3 4 5 6 7 8 9 10
2-1 6-5
2-1 6-5
1 2 3 4 5 6 7 8 9 10
0
6-1 8-3 10-5
1 2 3 4 5 6
2-3
2-1 4-3 6-4
1 2 3 4 5 6 7 8 9 10
2-1 6-5
2-1 6-5 7-2
1 2 3 4 5 6 7 8 9 10
0
3-5 4-1
1 2 3 4 5 6 7 8 9 10
2-1
2-1 6-5
1 2 3 4 5 6 7 8 9 10
0
6-1 8-3 10-5
1 2 3 4 5 6
2-3
2-1 4-3 6-4
1 2 3 4 5 6 7 8 9 10
2-1 6-5
2-1 6-5 7-2
1 2 3 4 5 6 7 8 9 10
0
3-5 4-1
1 2 3 4 5 6 7 8 9 10
2-1
2-1 6-5
1 2 3 4 5 6 7 8 9 10
0
6-1 8-3 10-5
1 2 3 4 5 6
2-3
2-1 4-3 6-4
1 2 3 4 5 6 7 8 9 10
2-1 6-5
2-1 6-5 7-2
1 2 3 4 5 6 7 8 9 10
0
输出
1 2 1 6 1 4 3 7 2 3 5 6 5 6 1 4 3 7 2 3 5 6 5 6 1 4 3 7 2 3
输入
3
1 2
1-2
2-1
1 2
1-2
2-1
1 2 3
2-3
输出
-1
设备2只能通过端口号2连上设备3的端口1这条线路,但是设备3中的端口1找不见右端口去连接了(剩余的端口2跟3已经互相连接)。因此找不见一条连接线。
输入
3
1 2 3 4 5 6 7 8 9 10
1-2 5-6
2-1 6-5
1 2 3 4 5 6 7 8 9 10
0
6-1 8-3 10-5
1 2 3 4 5 6
3-2
输出
1 2 1 6 1 4
按示例图中计算的权重最高的线路为1 2 1 6 1 4