P3643.第3题-寻找设备最优的连接线
题目内容
现有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
样例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
样例2
输入
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
输入
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
