题目链接

古代符文路径的激活

题目描述

在一个由 块符文石组成的线性系统中，需要找到一条从第 1 块到第 块的“最和谐”激活路径。

  • 系统结构： 块符文石，每块石头上有若干编号不同的铭文。
  • 能量流动：能量在相邻石头间通过“能量桥”流动，在石头内部通过“内部灵脉”流动。一条路径在每块石头 上都选定一个输入铭文 和一个输出铭文 。能量从石头 的 通过能量桥流到石头 的 ，再通过灵脉从 流到 。
  • 和谐度：路径的优劣通过字典序比较决定。比较从第 1 块石头开始，逐石对比。单块石头的和谐度由一个三元组 (, , ) 决定，字典序越小越优。其中 为 1 表示新建灵脉，0 表示使用已有灵脉。

任务是输出最和谐路径经过的所有铭文序列，如果不存在完整路径，则输出 -1。

解题思路

这是一个寻找最优路径的问题，其“成本”是字典序，并且决策是分阶段（逐个符文石）进行的。这种结构非常适合使用动态规划（Dynamic Programming）来解决。

我们可以将问题看作是在一个分层图上寻找最短路径，其中“最短”由字典序定义。

  1. DP 状态设计： 我们定义一个 DP 状态 ，它存储的是从第 1 块符文石开始，一直延伸到第 块符文石，并以其上的铭文 作为输出铭文的“最和谐”路径信息。这个信息需要包含两个部分：

    • 到目前为止的完整和谐度评分序列（一个由三元组构成的向量）。
    • 构成这条路径的铭文对序列 (, )。

  2. DP 转移方程： 我们逐块符文石（从 到 ）来构建 DP 表。

    • 基础情况 ()：对于第一块符文石，它没有前驱。因此，对于其上每一个可能的输出铭文 ，我们遍历所有其他铭文作为输入 ，计算出各自的和谐度评分，选择最优的一个 (, ) 组合，并将其路径信息存入 。

    • 递推情况 ()：要计算 ，我们依赖于 的结果。可以分两步进行： a. 计算最佳抵达：对于第 块符文石上的每一个铭文 ，我们需要找到抵达它的最优方式。这需要考察所有连接到 的能量桥 (, )，并从所有对应的 中，选出字典序最小的那条路径作为抵达 的最佳“前序路径”。 b. 计算当前石头最优路径：有了所有输入的最佳前序路径后，我们便可以计算 。对于第 块石头上每一个可能的输出铭文 ，我们遍历所有可能的输入铭文 。将 的最佳前序路径与当前石头的选择 (, ) 结合，形成一条完整的候选路径。在所有候选路径中，选择字典序最优的那条，存入 。

  3. 求解最终答案： 当 DP 表计算到第 层（最后一块符文石）后， 就包含了所有能走完全程的路径的最终信息。我们只需遍历 中的所有条目，找到那条拥有全局最小字典序评分的路径。如果 为空，则说明没有一条路径能贯穿始终，输出 -1。否则，按顺序输出最优路径中的所有铭文即可。

这种 DP 方法的复杂度大约为 ，其中 是符文石的数量， 是单个符文石上铭文的最大数量。考虑到 较小，该复杂度是可接受的。

代码

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <set>
#include <map>
#include <tuple>
#include <algorithm>
#include <optional>

using namespace std;

// 和谐度评分
using Score = tuple<int, int, int>;
// 路径由一系列 (输入, 输出) 铭文对组成
using Path = vector<pair<int, int>>;

// 存储一条完整路径及其评分
struct PathInfo {
    vector<Score> scores;
    Path path;

    // 字典序比较
    bool operator<(const PathInfo& other) const {
        return scores < other.scores;
    }
};

// 解析以空格分隔的整数行
void parse_line_to_set(const string& line, set<int>& s) {
    stringstream ss(line);
    int num;
    while (ss >> num) {
        s.insert(num);
    }
}

// 解析 "a-b" 格式的内部灵脉
void parse_ley_lines(const string& line, set<pair<int, int>>& container) {
    if (line == "0") return;
    stringstream ss(line);
    string pair_str;
    while (ss >> pair_str) {
        size_t dash_pos = pair_str.find('-');
        int u = stoi(pair_str.substr(0, dash_pos));
        int v = stoi(pair_str.substr(dash_pos + 1));
        container.insert({min(u, v), max(u, v)});
    }
}

// 解析 "a-b" 格式的能量桥
void parse_bridges(const string& line, map<int, vector<int>>& container) {
    if (line == "0") return;
    stringstream ss(line);
    string pair_str;
    while (ss >> pair_str) {
        size_t dash_pos = pair_str.find('-');
        int u = stoi(pair_str.substr(0, dash_pos));
        int v = stoi(pair_str.substr(dash_pos + 1));
        container[u].push_back(v);
    }
}

Score calculate_score(int in, int out, const set<pair<int, int>>& leys) {
    int is_new = 1;
    if (leys.count({min(in, out), max(in, out)})) {
        is_new = 0;
    }
    return make_tuple(is_new, in + out, in);
}

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

    int n;
    string line;
    getline(cin, line);
    n = stoi(line);

    vector<set<int>> inscriptions(n);
    vector<set<pair<int, int>>> ley_lines(n);
    vector<set<int>> occupied_ports(n); // 记录被古老灵脉占用的铭文
    vector<map<int, vector<int>>> bridges(n - 1);

    for (int i = 0; i < n; ++i) {
        getline(cin, line);
        parse_line_to_set(line, inscriptions[i]);
        
        getline(cin, line);
        set<pair<int, int>> current_leys;
        parse_ley_lines(line, current_leys);
        ley_lines[i] = current_leys;
        for(const auto& p : current_leys) {
            occupied_ports[i].insert(p.first);
            occupied_ports[i].insert(p.second);
        }

        if (i < n - 1) {
            getline(cin, line);
            parse_bridges(line, bridges[i]);
        }
    }

    vector<map<int, PathInfo>> dp(n);

    // 基础情况：处理第 0 块符文石
    for (int out_p : inscriptions[0]) {
        optional<PathInfo> best_pi;
        for (int in_p : inscriptions[0]) {
            if (in_p == out_p) continue;
            
            bool is_existing = ley_lines[0].count({min(in_p, out_p), max(in_p, out_p)});
            if (!is_existing && (occupied_ports[0].count(in_p) || occupied_ports[0].count(out_p))) {
                continue; // 新建灵脉不能使用被占用的铭文
            }

            Score score = calculate_score(in_p, out_p, ley_lines[0]);
            PathInfo current_pi{{score}, {{in_p, out_p}}};
            if (!best_pi.has_value() || current_pi < best_pi.value()) {
                best_pi = current_pi;
            }
        }
        if (best_pi.has_value()) {
            dp[0][out_p] = best_pi.value();
        }
    }

    // DP 过程：处理第 1 到 n-1 块符文石
    for (int i = 1; i < n; ++i) {
        map<int, PathInfo> best_arrival;
        for (auto const& [prev_out, prev_pi] : dp[i - 1]) {
            if (bridges[i - 1].count(prev_out)) {
                for (int current_in : bridges[i - 1].at(prev_out)) {
                    if (inscriptions[i].count(current_in)) {
                         if (!best_arrival.count(current_in) || prev_pi < best_arrival.at(current_in)) {
                            best_arrival[current_in] = prev_pi;
                        }
                    }
                }
            }
        }

        for (int out_p : inscriptions[i]) {
            optional<PathInfo> best_pi_for_out;
            for (auto const& [in_p, arrival_pi] : best_arrival) {
                if (in_p == out_p) continue;

                bool is_existing = ley_lines[i].count({min(in_p, out_p), max(in_p, out_p)});
                if (!is_existing && (occupied_ports[i].count(in_p) || occupied_ports[i].count(out_p))) {
                    continue; // 新建灵脉不能使用被占用的铭文
                }

                PathInfo candidate_pi = arrival_pi;
                candidate_pi.scores.push_back(calculate_score(in_p, out_p, ley_lines[i]));
                candidate_pi.path.push_back({in_p, out_p});

                if (!best_pi_for_out.has_value() || candidate_pi < best_pi_for_out.value()) {
                    best_pi_for_out = candidate_pi;
                }
            }
            if (best_pi_for_out.has_value()) {
                dp[i][out_p] = best_pi_for_out.value();
            }
        }
    }

    optional<PathInfo> final_best_pi;
    if (!dp[n - 1].empty()) {
        for (auto const& [out_p, pi] : dp[n - 1]) {
            if (!final_best_pi.has_value() || pi < final_best_pi.value()) {
                final_best_pi = pi;
            }
        }
    }

    if (final_best_pi.has_value()) {
        bool first = true;
        for (const auto& p : final_best_pi.value().path) {
            if (!first) cout << " ";
            cout << p.first << " " << p.second;
            first = false;
        }
        cout << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}

import java.util.*;

public class Main {

    static class Score implements Comparable<Score> {
        int isNew, sum, in;

        Score(int isNew, int sum, int in) {
            this.isNew = isNew;
            this.sum = sum;
            this.in = in;
        }

        @Override
        public int compareTo(Score other) {
            if (this.isNew != other.isNew) return Integer.compare(this.isNew, other.isNew);
            if (this.sum != other.sum) return Integer.compare(this.sum, other.sum);
            return Integer.compare(this.in, other.in);
        }
    }

    static class PathInfo implements Comparable<PathInfo> {
        List<Score> scores;
        List<int[]> path;

        PathInfo() {
            this.scores = new ArrayList<>();
            this.path = new ArrayList<>();
        }
        
        PathInfo(PathInfo other) {
            this.scores = new ArrayList<>(other.scores);
            this.path = new ArrayList<>(other.path);
        }

        @Override
        public int compareTo(PathInfo other) {
            int size = Math.min(this.scores.size(), other.scores.size());
            for (int i = 0; i < size; i++) {
                int cmp = this.scores.get(i).compareTo(other.scores.get(i));
                if (cmp != 0) return cmp;
            }
            return Integer.compare(this.scores.size(), other.scores.size());
        }
    }
    
    static Score calculateScore(int in, int out, Set<String> leys) {
        int isNew = leys.contains(Math.min(in, out) + "-" + Math.max(in, out)) ? 0 : 1;
        return new Score(isNew, in + out, in);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());

        List<Set<Integer>> inscriptions = new ArrayList<>();
        List<Set<String>> leyLines = new ArrayList<>();
        List<Set<Integer>> occupiedPorts = new ArrayList<>(); // 新增
        List<Map<Integer, List<Integer>>> bridges = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            inscriptions.add(new HashSet<>());
            String[] parts = sc.nextLine().split(" ");
            for(String s : parts) inscriptions.get(i).add(Integer.parseInt(s));

            leyLines.add(new HashSet<>());
            occupiedPorts.add(new HashSet<>());
            String leyLine = sc.nextLine();
            if (!leyLine.equals("0")) {
                parts = leyLine.split(" ");
                for (String p : parts) {
                    String[] nums = p.split("-");
                    int u = Integer.parseInt(nums[0]);
                    int v = Integer.parseInt(nums[1]);
                    leyLines.get(i).add(Math.min(u, v) + "-" + Math.max(u, v));
                    occupiedPorts.get(i).add(u);
                    occupiedPorts.get(i).add(v);
                }
            }

            if (i < n - 1) {
                bridges.add(new HashMap<>());
                String bridgeLine = sc.nextLine();
                if (!bridgeLine.equals("0")) {
                    parts = bridgeLine.split(" ");
                    for (String p : parts) {
                        String[] nums = p.split("-");
                        int u = Integer.parseInt(nums[0]);
                        int v = Integer.parseInt(nums[1]);
                        bridges.get(i).computeIfAbsent(u, k -> new ArrayList<>()).add(v);
                    }
                }
            }
        }

        List<Map<Integer, PathInfo>> dp = new ArrayList<>();
        for(int i = 0; i < n; i++) dp.add(new HashMap<>());

        // Base case
        for (int outP : inscriptions.get(0)) {
            PathInfo bestPi = null;
            for (int inP : inscriptions.get(0)) {
                if (inP == outP) continue;

                boolean isExisting = leyLines.get(0).contains(Math.min(inP, outP) + "-" + Math.max(inP, outP));
                if (!isExisting && (occupiedPorts.get(0).contains(inP) || occupiedPorts.get(0).contains(outP))) {
                    continue; // 新建灵脉不能使用被占用的铭文
                }

                PathInfo currentPi = new PathInfo();
                currentPi.scores.add(calculateScore(inP, outP, leyLines.get(0)));
                currentPi.path.add(new int[]{inP, outP});
                if (bestPi == null || currentPi.compareTo(bestPi) < 0) {
                    bestPi = currentPi;
                }
            }
            if (bestPi != null) {
                dp.get(0).put(outP, bestPi);
            }
        }
        
        // DP
        for (int i = 1; i < n; i++) {
            Map<Integer, PathInfo> bestArrival = new HashMap<>();
            for (Map.Entry<Integer, PathInfo> entry : dp.get(i - 1).entrySet()) {
                int prevOut = entry.getKey();
                PathInfo prevPi = entry.getValue();
                if (bridges.get(i - 1).containsKey(prevOut)) {
                    for (int currentIn : bridges.get(i-1).get(prevOut)) {
                        if (inscriptions.get(i).contains(currentIn)) {
                            if (!bestArrival.containsKey(currentIn) || prevPi.compareTo(bestArrival.get(currentIn)) < 0) {
                                bestArrival.put(currentIn, prevPi);
                            }
                        }
                    }
                }
            }

            for (int outP : inscriptions.get(i)) {
                PathInfo bestPiForOut = null;
                for (Map.Entry<Integer, PathInfo> entry : bestArrival.entrySet()) {
                    int inP = entry.getKey();
                    if (inP == outP) continue;
                    
                    boolean isExisting = leyLines.get(i).contains(Math.min(inP, outP) + "-" + Math.max(inP, outP));
                    if (!isExisting && (occupiedPorts.get(i).contains(inP) || occupiedPorts.get(i).contains(outP))) {
                        continue; // 新建灵脉不能使用被占用的铭文
                    }

                    PathInfo arrivalPi = entry.getValue();
                    PathInfo candidatePi = new PathInfo(arrivalPi);
                    candidatePi.scores.add(calculateScore(inP, outP, leyLines.get(i)));
                    candidatePi.path.add(new int[]{inP, outP});

                    if (bestPiForOut == null || candidatePi.compareTo(bestPiForOut) < 0) {
                        bestPiForOut = candidatePi;
                    }
                }
                if (bestPiForOut != null) {
                    dp.get(i).put(outP, bestPiForOut);
                }
            }
        }
        
        PathInfo finalBestPi = null;
        if (!dp.get(n - 1).isEmpty()) {
            for (PathInfo pi : dp.get(n - 1).values()) {
                if (finalBestPi == null || pi.compareTo(finalBestPi) < 0) {
                    finalBestPi = pi;
                }
            }
        }

        if (finalBestPi != null) {
            StringJoiner sj = new StringJoiner(" ");
            for(int[] p : finalBestPi.path) {
                sj.add(String.valueOf(p[0]));
                sj.add(String.valueOf(p[1]));
            }
            System.out.println(sj.toString());
        } else {
            System.out.println(-1);
        }
    }
}

import sys

def parse_line_to_set(line):
    if not line.strip(): return set()
    return set(map(int, line.split()))

def parse_pair_line(line, is_bridge=False):
    if line.strip() == "0":
        return {} if is_bridge else set()
    
    if is_bridge:
        container = {}
        for part in line.split():
            u, v = map(int, part.split('-'))
            if u not in container:
                container[u] = []
            container[u].append(v)
        return container
    else: # 内部灵脉
        container = set()
        for part in line.split():
            u, v = map(int, part.split('-'))
            container.add(tuple(sorted((u, v))))
        return container

def calculate_score(in_p, out_p, leys):
    is_new = 0 if tuple(sorted((in_p, out_p))) in leys else 1
    return (is_new, in_p + out_p, in_p)

def main():
    n = int(input())
    
    inscriptions = []
    ley_lines = []
    occupied_ports = [] # 新增
    bridges = []
    
    for i in range(n):
        inscriptions.append(parse_line_to_set(input()))
        
        current_leys = parse_pair_line(input())
        ley_lines.append(current_leys)
        
        current_occupied = set()
        for u, v in current_leys:
            current_occupied.add(u)
            current_occupied.add(v)
        occupied_ports.append(current_occupied)
        
        if i < n - 1:
            bridges.append(parse_pair_line(input(), is_bridge=True))
            
    dp = [{} for _ in range(n)]

    # 基础情况：处理第 0 块符文石
    for out_p in inscriptions[0]:
        best_pi = None
        for in_p in inscriptions[0]:
            if in_p == out_p:
                continue
            
            is_existing = tuple(sorted((in_p, out_p))) in ley_lines[0]
            if not is_existing and (in_p in occupied_ports[0] or out_p in occupied_ports[0]):
                continue # 新建灵脉不能使用被占用的铭文

            score = calculate_score(in_p, out_p, ley_lines[0])
            # PathInfo 是一个元组：(评分列表, 路径列表)
            current_pi = ([score], [(in_p, out_p)])
            if best_pi is None or current_pi[0] < best_pi[0]:
                best_pi = current_pi
        if best_pi:
            dp[0][out_p] = best_pi
            
    # DP 过程：处理第 1 到 n-1 块符文石
    for i in range(1, n):
        best_arrival = {}
        for prev_out, prev_pi in dp[i - 1].items():
            if prev_out in bridges[i - 1]:
                for current_in in bridges[i-1][prev_out]:
                    if current_in in inscriptions[i]:
                        if current_in not in best_arrival or prev_pi[0] < best_arrival[current_in][0]:
                            best_arrival[current_in] = prev_pi
        
        for out_p in inscriptions[i]:
            best_pi_for_out = None
            for in_p, arrival_pi in best_arrival.items():
                if in_p == out_p:
                    continue
                
                is_existing = tuple(sorted((in_p, out_p))) in ley_lines[i]
                if not is_existing and (in_p in occupied_ports[i] or out_p in occupied_ports[i]):
                    continue # 新建灵脉不能使用被占用的铭文

                score = calculate_score(in_p, out_p, ley_lines[i])
                candidate_scores = arrival_pi[0] + [score]
                candidate_path = arrival_pi[1] + [(in_p, out_p)]
                candidate_pi = (candidate_scores, candidate_path)

                if best_pi_for_out is None or candidate_pi[0] < best_pi_for_out[0]:
                    best_pi_for_out = candidate_pi
            
            if best_pi_for_out:
                dp[i][out_p] = best_pi_for_out

    final_best_pi = None
    if dp[n - 1]:
        for pi in dp[n - 1].values():
            if final_best_pi is None or pi[0] < final_best_pi[0]:
                final_best_pi = pi
    
    if final_best_pi:
        result = []
        for in_p, out_p in final_best_pi[1]:
            result.append(str(in_p))
            result.append(str(out_p))
        print(" ".join(result))
    else:
        print(-1)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：动态规划 (Dynamic Programming)
  • 时间复杂度： - 其中 是符文石的数量， 是单个符文石上铭文的最大数量。DP 过程有 个阶段，每个阶段的计算复杂度约为 ， 用于遍历当前石头上的铭文对，而乘以 是因为路径评分向量的比较和复制成本与路径长度（最多为 ）成正比。
  • 空间复杂度： - DP 表需要存储 块石头的信息，每块石头最多 个出口，每个出口路径的长度最多为 。