解法思路

把输入抽象为三组数据：

• S_i：第 i 层的候选集合；
• pair_i：第 i 层的无向配对表；
• trans_i：第 i 层的跨层映射（到第 i+1 层），末层为恒等。

接着做一层深度优先搜索（DFS / 回溯）：

• 外层：起点 s0 的选择有先后顺序。按照下述排序尝试 S_0：

  1. 优先尝试那些“在 pair_0 中出现过的点”（有配对的起点）；
  2. 次序再按 x + pair_0.get(x, 0) 的和从小到大；
  3. 再按 x 升序。 这是对你代码里起点排序规则的语义化复现。

• 内层：在层 i 已知当前状态 s_i 时，

  • 若存在“配对优先”的合法分支（pair_i[s_i] 同时也是 trans_i 的键），先走它；
  • 否则枚举 trans_i 的所有键（升序），作为兜底分支，做一些轻量剪枝（x != s_i、x 不在 pair_i 的键集中、以及可选的“像集”剪枝）。

由于搜索深度固定为 n，并且每层枚举的是一个有限升序集，回溯很快；且一旦找到首个解即可输出。

正确性要点

• 若某层存在“配对优先”分支，它与同层配对约束完全吻合，并且能直接把状态推进到下一层（trans_i 完整性保证）。
• 否则兜底分支遍历 trans_i 的所有合法键，穷尽所有可行的非优先选择；轻量剪枝只排除明显无谓或易冲突的尝试，不会剔除真正可行解。
• 以有序方式枚举，保证输出是按题中（或约定）优先级得到的字典序最优解（与给定代码的搜索顺序保持一致的效果）。

复杂度

• 记第 i 层 trans_i 的 key 数为 m_i。最坏回溯复杂度约 O(∏ m_i)，但由于有“配对优先”与轻量剪枝，实际很快。
• 额外的排序开销为 O(m_i log m_i) 量级。

实现要点

• 输入的“配对行”“映射行”用空格分隔，0 表示结束；u-v 表示一条边或配对。
• 末层 i == n-1 的跨层映射为恒等 x -> x。
• 若 i < n-1 且跨层映射为空，立即输出 -1 并结束。
• 输出时打印构造路径里除了最后一个状态之外的所有数字。

C++ 实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    auto read_nonempty = [&]() {
        string s;
        getline(cin, s);
        while (s.size() == 0 && !cin.fail()) getline(cin, s);
        return s;
    };

    string fs = read_nonempty();
    if (fs.empty()) return 0;
    int n = stoi(fs);

    vector<vector<int>> S(n);
    vector<unordered_map<int,int>> pair_tab(n);
    vector<unordered_map<int,int>> trans(n);

    for (int i = 0; i < n; ++i) {
        {   // 候选集
            string line = read_nonempty();
            stringstream ss(line);
            int x;
            while (ss >> x) S[i].push_back(x);
        }
        {   // 同层无向配对
            string line = read_nonempty();
            stringstream ss(line);
            string tok;
            while (ss >> tok) {
                if (tok == "0") break;
                auto pos = tok.find('-');
                int u = stoi(tok.substr(0, pos));
                int v = stoi(tok.substr(pos + 1));
                pair_tab[i][u] = v;
                pair_tab[i][v] = u;
            }
        }
        if (i < n - 1) {
            string line = read_nonempty();
            stringstream ss(line);
            string tok;
            while (ss >> tok) {
                if (tok == "0") break;
                auto pos = tok.find('-');
                int u = stoi(tok.substr(0, pos));
                int v = stoi(tok.substr(pos + 1));
                trans[i][u] = v;
            }
            if (trans[i].empty()) { cout << -1 << "\n"; return 0; }
        } else {
            for (int x : S[i]) trans[i][x] = x; // 末层恒等
        }
    }

    // 每层键的升序
    vector<vector<int>> keys(n);
    for (int i = 0; i < n; ++i) {
        for (auto &kv : trans[i]) keys[i].push_back(kv.first);
        sort(keys[i].begin(), keys[i].end());
    }

    // 倒数第二层像集（若存在）
    unordered_set<int> last_values;
    if (n >= 2) {
        for (auto &kv : trans[n - 2]) last_values.insert(kv.second);
    }

    // 起点排序：有配对优先 -> (x + pair[x]) -> x
    vector<int> starts = S[0];
    sort(starts.begin(), starts.end(), [&](int a, int b){
        int pa = pair_tab[0].count(a) ? 0 : 1;
        int pb = pair_tab[0].count(b) ? 0 : 1;
        if (pa != pb) return pa < pb;
        int sa = a + (pair_tab[0].count(a) ? pair_tab[0].at(a) : 0);
        int sb = b + (pair_tab[0].count(b) ? pair_tab[0].at(b) : 0);
        if (sa != sb) return sa < sb;
        return a < b;
    });

    vector<long long> answer;
    bool found = false;

    function<void(int,int,vector<long long>&)> dfs = [&](int layer, int cur, vector<long long> &path){
        if (found) return;
        if (layer == n) { answer = path; found = true; return; }

        // 配对优先
        auto itp = pair_tab[layer].find(cur);
        if (itp != pair_tab[layer].end()) {
            int mate = itp->second;
            auto it = trans[layer].find(mate);
            if (it != trans[layer].end()) {
                int nxt = it->second;
                path.push_back(mate);
                path.push_back(nxt);
                dfs(layer + 1, nxt, path);
                path.pop_back(); path.pop_back();
                if (found) return;
            }
        }

        // 兜底（含“倒数第二层像集”过滤）
        for (int x : keys[layer]) {
            if (x == cur) continue;
            if (pair_tab[layer].count(x)) continue;
            if (layer > 0 && last_values.count(x)) continue;

            int nxt = trans[layer][x];
            path.push_back(x);
            path.push_back(nxt);
            dfs(layer + 1, nxt, path);
            path.pop_back(); path.pop_back();
            if (found) return;
        }
    };

    for (int s0 : starts) {
        vector<long long> path = {(long long)s0};
        dfs(0, s0, path);
        if (found) {
            for (size_t i = 0; i + 1 < answer.size(); ++i) {
                if (i) cout << ' ';
                cout << answer[i];
            }
            cout << "\n";
            return 0;
        }
    }
    cout << -1 << "\n";
    return 0;
}

Python 实现

import sys

def solve():
    def read_line():
        return sys.stdin.readline().strip()

    n = int(read_line())
    levels = []
    pair_tab = []
    trans = []

    # 读取：候选集 S_i、同层无向配对 pair_i、跨层映射 trans_i（末层恒等）
    for i in range(n):
        levels.append(list(map(int, read_line().split())))

        tokens = read_line().split()
        undirected = {}
        for tk in tokens:
            if tk == "0": break
            u, v = map(int, tk.split('-'))
            undirected[u] = v
            undirected[v] = u
        pair_tab.append(undirected)

        if i < n - 1:
            tokens = read_line().split()
            to_next = {}
            for tk in tokens:
                if tk == "0": break
                u, v = map(int, tk.split('-'))
                to_next[u] = v
            if not to_next:
                print(-1)
                return
            trans.append(to_next)
        else:
            trans.append({x: x for x in levels[-1]})

    # 每层键的升序列表
    keys = [sorted(trans[i].keys()) for i in range(n)]

    # 关键修正：使用“倒数第二层”的像集作为全局过滤集合（若存在）
    last_values = set(trans[n - 2].values()) if n >= 2 else set()

    # 起点排序：有配对优先 -> (x + pair[x]) 小 -> x 小
    def start_order(x):
        has_pair = 0 if x in pair_tab[0] else 1
        pair_sum = x + pair_tab[0].get(x, 0)
        return (has_pair, pair_sum, x)

    starts = sorted(levels[0], key=start_order)

    sys.setrecursionlimit(1 << 25)
    ans_path = []
    done = False

    def dfs(layer, cur, path):
        nonlocal ans_path, done
        if done:
            return
        if layer == n:
            ans_path = path[:]
            done = True
            return

        # 1) 配对优先：cur 的配对点存在且可映射
        mate = pair_tab[layer].get(cur)
        if mate is not None and mate in trans[layer]:
            nxt = trans[layer][mate]
            path.extend([mate, nxt])
            dfs(layer + 1, nxt, path)
            path.pop(); path.pop()
            if done: return

        # 2) 兜底分支：按键升序尝试；使用“倒数第二层像集”的过滤（layer>0 时）
        for x in keys[layer]:
            if x == cur:            # 不能自选
                continue
            if x in pair_tab[layer]:# 若 x 在配对表里，让“配对优先”去处理
                continue
            if layer > 0 and x in last_values:
                continue

            nxt = trans[layer][x]
            path.extend([x, nxt])
            dfs(layer + 1, nxt, path)
            path.pop(); path.pop()
            if done: return

    for s0 in starts:
        dfs(0, s0, [s0])
        if done:
            print(*ans_path[:-1])  # 最后一个状态不输出
            return
    print(-1)

if __name__ == "__main__":
    solve()

Java

import java.io.*;
import java.util.*;

public class Main {
    static String readLine(BufferedReader br) throws IOException {
        String s = br.readLine();
        while (s != null && s.length() == 0) s = br.readLine();
        return s == null ? "" : s;
    }

    static Map<Integer,Integer> parsePairs(String line, boolean undirected) {
        Map<Integer,Integer> mp = new HashMap<>();
        if (line == null || line.isEmpty()) return mp;
        String[] toks = line.trim().split("\\s+");
        for (String tk : toks) {
            if (tk.equals("0")) break;
            int pos = tk.indexOf('-');
            int u = Integer.parseInt(tk.substring(0, pos));
            int v = Integer.parseInt(tk.substring(pos + 1));
            if (undirected) { mp.put(u, v); mp.put(v, u); }
            else mp.put(u, v);
        }
        return mp;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String first = readLine(br);
        if (first.isEmpty()) return;
        int n = Integer.parseInt(first);

        List<List<Integer>> S = new ArrayList<>();
        List<Map<Integer,Integer>> pairTab = new ArrayList<>();
        List<Map<Integer,Integer>> trans = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            // 候选集
            {
                String l = readLine(br);
                String[] ss = l.trim().split("\\s+");
                List<Integer> arr = new ArrayList<>();
                for (String t : ss) if (!t.isEmpty()) arr.add(Integer.parseInt(t));
                S.add(arr);
            }
            // 无向配对
            {
                String l = readLine(br);
                pairTab.add(parsePairs(l, true));
            }
            // 跨层映射
            if (i < n - 1) {
                String l = readLine(br);
                Map<Integer,Integer> toNext = parsePairs(l, false);
                if (toNext.isEmpty()) { System.out.println(-1); return; }
                trans.add(toNext);
            } else {
                Map<Integer,Integer> last = new HashMap<>();
                for (int x : S.get(i)) last.put(x, x);
                trans.add(last);
            }
        }

        // 每层键升序
        List<List<Integer>> keys = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<Integer> ks = new ArrayList<>(trans.get(i).keySet());
            Collections.sort(ks);
            keys.add(ks);
        }

        // 倒数第二层像集
        Set<Integer> lastValues = new HashSet<>();
        if (n >= 2) lastValues.addAll(trans.get(n - 2).values());

        // 起点排序：有配对优先 -> (x + pair[x]) -> x
        List<Integer> starts = new ArrayList<>(S.get(0));
        starts.sort((a, b) -> {
            int pa = pairTab.get(0).containsKey(a) ? 0 : 1;
            int pb = pairTab.get(0).containsKey(b) ? 0 : 1;
            if (pa != pb) return pa - pb;
            int sa = a + pairTab.get(0).getOrDefault(a, 0);
            int sb = b + pairTab.get(0).getOrDefault(b, 0);
            if (sa != sb) return sa - sb;
            return Integer.compare(a, b);
        });

        List<Long> ans = new ArrayList<>();
        boolean[] done = {false};

        class DFS {
            void go(int layer, int cur, List<Long> path) {
                if (done[0]) return;
                if (layer == n) {
                    ans.clear();
                    ans.addAll(path);
                    done[0] = true;
                    return;
                }

                Map<Integer,Integer> pt = pairTab.get(layer);
                Map<Integer,Integer> tr = trans.get(layer);

                // 配对优先
                if (pt.containsKey(cur)) {
                    int mate = pt.get(cur);
                    if (tr.containsKey(mate)) {
                        int nxt = tr.get(mate);
                        path.add((long)mate);
                        path.add((long)nxt);
                        go(layer + 1, nxt, path);
                        path.remove(path.size() - 1);
                        path.remove(path.size() - 1);
                        if (done[0]) return;
                    }
                }

                // 兜底 + 倒数第二层像集过滤
                for (int x : keys.get(layer)) {
                    if (x == cur) continue;
                    if (pt.containsKey(x)) continue;
                    if (layer > 0 && lastValues.contains(x)) continue;

                    int nxt = tr.get(x);
                    path.add((long)x);
                    path.add((long)nxt);
                    go(layer + 1, nxt, path);
                    path.remove(path.size() - 1);
                    path.remove(path.size() - 1);
                    if (done[0]) return;
                }
            }
        }

        DFS solver = new DFS();
        for (int s0 : starts) {
            List<Long> path = new ArrayList<>();
            path.add((long)s0);
            solver.go(0, s0, path);
            if (done[0]) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i + 1 < ans.size(); i++) {
                    if (i > 0) sb.append(' ');
                    sb.append(ans.get(i));
                }
                System.out.println(sb.toString());
                return;
            }
        }

        System.out.println(-1);
    }
}

题目内容

现有$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$