题解 | #星途勘测#

题目链接

星途勘测

题目描述

给定一个由 $n$ 颗恒星和 $m$ 条星途（边）组成的无向图。每条星途按输入顺序被唯一编号。我们需要找出所有从启程之星 $s$ 到圣地之星 $t$ 的简单路径（路径上恒星与星途均不重复）。

所有找到的简单路径，根据其经过的星途编号序列，进行字典序升序排列，并赋予一个从 1 开始的唯一索引。

接下来，会有 $q$ 场宇宙风暴，每场风暴会摧毁一条星途。对于每次风暴，需要报告出所有被切断的朝圣路线的索引。

输入:

第一行包含四个整数 $n, m, s, t$ 。
接下来 $m$ 行，描述 $m$ 条星途。
之后一行是一个整数 $q$ ，代表风暴总次数。
最后 $q$ 行，每行一个整数，代表被摧毁的星途编号。

输出:

针对 $q$ 次风暴，输出 $q$ 行答案。每行先输出被切断的路线总数，然后升序输出这些路线的索引。

解题思路

本题的核心在于处理图的路径问题，并快速响应查询。由于题目保证从 $s$ 到 $t$ 的简单路径总数不超过 10,000 条，这提示我们可以预处理所有的路径。

整体思路分为三步：

寻找所有简单路径：
- 使用深度优先搜索 (DFS) 是寻找图中所有简单路径的经典方法。
- 我们需要一个 dfs 函数，它在图上进行探索，同时记录当前路径经过的星途编号。
- 为了确保路径是“简单”的，即不重复经过节点和边，我们需要在DFS的每一层递归中，维护一个访问过的节点集合 $visited\_nodes$ 和一个访问过的边集合 $visited\_edges$ 。
- 当DFS搜索到达终点 $t$ 时，我们就找到了一条完整的简单路径，将其星途编号序列保存起来。
建立索引：
- 将所有找到的路径（星途编号序列）收集起来后，按照字典序进行升序排序。这 دقیقا 对应了题目中“星图法典”的排序方式。
- 为了能快速响应查询，我们建立一个“倒排索引”。具体来说，是创建一个从“星途编号”到“包含该星途的路径索引列表”的映射。我们可以用一个 map 或哈希表 $edge\_to\_paths$ 来实现。
- 遍历排序后的所有路径，对于第 $i$ 条路径（其索引为 $i+1$ ），我们将 $i+1$ 添加到该路径所包含的每一条星途 $e$ 对应的映射列表 $edge\_to\_paths[e]$ 中。由于我们是按路径索引顺序添加的，每个列表中的索引自然就是升序的。
处理风暴查询：
- 经过上述预处理，处理查询就变得非常简单。
- 对于每一次风暴，给定被摧毁的星途编号 $e_{destroyed}$ ，我们直接在倒排索引 $edge\_to\_paths$ 中查找 $e_{destroyed}$ 。
- 其对应的列表就包含了所有被切断的路径索引。我们只需按格式输出该列表的大小和内容即可。

通过这种“预处理+查询”的模式，我们可以高效地解决问题。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

// 图的邻接表表示，存储<邻居节点, 边的ID>
vector<pair<int, int>> adj[501];
// 存储所有从 s 到 t 的简单路径
vector<vector<int>> all_paths;
// 访问标记数组
bool visited_nodes[501];
bool visited_edges[1001];

// DFS 寻找所有简单路径
void dfs(int u, int t, vector<int>& current_path) {
    // 1. 进入节点u，标记为已访问
    visited_nodes[u] = true;

    // 2. 判断是否到达终点
    if (u == t) {
        all_paths.push_back(current_path);
    } else {
        // 3. 如果不是终点，遍历邻居继续探索
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int edge_id = edge.second;
            // 确保邻居节点和边都未被访问
            if (!visited_nodes[v] && !visited_edges[edge_id]) {
                visited_edges[edge_id] = true;
                current_path.push_back(edge_id);
                
                dfs(v, t, current_path); // 递归调用
                
                // 递归返回后，回溯状态
                current_path.pop_back();
                visited_edges[edge_id] = false;
            }
        }
    }
    
    // 4. 所有从u出发的路径都探索完毕，将u标记为未访问，完成回溯
    visited_nodes[u] = false;
}

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

    int n, m, s, t;
    cin >> n >> m >> s >> t;

    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    // 优化：对每个节点的邻接表按边ID排序
    // 这样DFS会自然按字典序发现路径，避免最后对所有路径进行大排序
    for (int i = 1; i <= n; ++i) {
        sort(adj[i].begin(), adj[i].end(), [](const auto& a, const auto& b) {
            return a.second < b.second;
        });
    }

    vector<int> path;
    dfs(s, t, path);

    // 按字典序排序所有路径 (由于上面的优化，此步不再需要)
    // sort(all_paths.begin(), all_paths.end());

    // 建立倒排索引：edge_id -> list of path_indices
    map<int, vector<int>> edge_to_paths;
    for (int i = 0; i < all_paths.size(); ++i) {
        for (int edge_id : all_paths[i]) {
            edge_to_paths[edge_id].push_back(i + 1);
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int destroyed_edge;
        cin >> destroyed_edge;
        if (edge_to_paths.find(destroyed_edge) == edge_to_paths.end()) {
            cout << 0 << endl;
        } else {
            const auto& paths = edge_to_paths[destroyed_edge];
            cout << paths.size();
            for (int path_idx : paths) {
                cout << " " << path_idx;
            }
            cout << endl;
        }
    }

    return 0;
}

import java.util.*;

public class Main {
    static List<int[]>[] adj;
    static List<List<Integer>> allPaths = new ArrayList<>();
    static boolean[] visitedNodes;
    static boolean[] visitedEdges;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int s = sc.nextInt();
        int t = sc.nextInt();

        adj = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 1; i <= m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            adj[u].add(new int[]{v, i});
            adj[v].add(new int[]{u, i});
        }

        visitedNodes = new boolean[n + 1];
        visitedEdges = new boolean[m + 1];
        dfs(s, t, new ArrayList<>());

        // 按字典序排序
        allPaths.sort((p1, p2) -> {
            int len = Math.min(p1.size(), p2.size());
            for (int i = 0; i < len; i++) {
                if (!p1.get(i).equals(p2.get(i))) {
                    return p1.get(i) - p2.get(i);
                }
            }
            return p1.size() - p2.size();
        });

        // 建立倒排索引
        Map<Integer, List<Integer>> edgeToPaths = new HashMap<>();
        for (int i = 0; i < allPaths.size(); i++) {
            for (int edgeId : allPaths.get(i)) {
                edgeToPaths.computeIfAbsent(edgeId, k -> new ArrayList<>()).add(i + 1);
            }
        }

        int q = sc.nextInt();
        for (int i = 0; i < q; i++) {
            int destroyedEdge = sc.nextInt();
            List<Integer> affectedPaths = edgeToPaths.getOrDefault(destroyedEdge, new ArrayList<>());
            
            System.out.print(affectedPaths.size());
            for (int pathIdx : affectedPaths) {
                System.out.print(" " + pathIdx);
            }
            System.out.println();
        }
    }

    private static void dfs(int u, int t, List<Integer> currentPath) {
        visitedNodes[u] = true;
        if (u == t) {
            allPaths.add(new ArrayList<>(currentPath));
            visitedNodes[u] = false; // 回溯
            return;
        }

        for (int[] edge : adj[u]) {
            int v = edge[0];
            int edgeId = edge[1];
            if (!visitedNodes[v] && !visitedEdges[edgeId]) {
                visitedEdges[edgeId] = true;
                currentPath.add(edgeId);
                dfs(v, t, currentPath);
                // 回溯
                currentPath.remove(currentPath.size() - 1);
                visitedEdges[edgeId] = false;
            }
        }
        visitedNodes[u] = false; // 回溯
    }
}

import sys
from collections import defaultdict

# 增加递归深度限制
sys.setrecursionlimit(2000)

def dfs(u, t, current_path):
    visited_nodes[u] = True
    if u == t:
        all_paths.append(list(current_path))
        visited_nodes[u] = False  # 回溯
        return

    for v, edge_id in adj[u]:
        if not visited_nodes[v] and not visited_edges[edge_id]:
            visited_edges[edge_id] = True
            current_path.append(edge_id)
            dfs(v, t, current_path)
            # 回溯
            current_path.pop()
            visited_edges[edge_id] = False
    
    visited_nodes[u] = False  # 回溯

n, m, s, t = map(int, input().split())

adj = defaultdict(list)
for i in range(1, m + 1):
    u, v = map(int, input().split())
    adj[u].append((v, i))
    adj[v].append((u, i))

all_paths = []
visited_nodes = [False] * (n + 1)
visited_edges = [False] * (m + 1)

dfs(s, t, [])

# 按字典序排序
all_paths.sort()

# 建立倒排索引
edge_to_paths = defaultdict(list)
for i, path in enumerate(all_paths):
    for edge_id in path:
        edge_to_paths[edge_id].append(i + 1)

q = int(input())
for _ in range(q):
    destroyed_edge = int(input())
    affected_paths = edge_to_paths.get(destroyed_edge, [])
    
    print(len(affected_paths), *affected_paths)

算法及复杂度

算法：深度优先搜索 (DFS) + 排序 + 哈希表
时间复杂度：令 $P$ 为从 $s$ 到 $t$ 的简单路径总数， $L$ 为最长路径的长度。
- DFS寻找所有路径的复杂度与 $P \cdot L$ 相关。
- 对所有路径进行排序的复杂度为 $\mathcal{O}(P \cdot L \cdot \log P)$ 。
- 建立倒排索引的复杂度为 $\mathcal{O}(P \cdot L)$ 。
- $q$ 次查询的复杂度为 $\mathcal{O}(q \cdot k)$ ，其中 $k$ 是单次查询返回的路径数量，主要是输出开销。
- 总时间复杂度主要由排序决定，为 $\mathcal{O}(P \cdot L \cdot \log P)$ 。
空间复杂度：
- 存储图需要 $\mathcal{O}(n+m)$ 。
- 存储所有路径需要 $\mathcal{O}(P \cdot L)$ 。
- 存储倒排索引最坏情况下也需要 $\mathcal{O}(P \cdot L)$ 。
- 总空间复杂度为 $\mathcal{O}(n + m + P \cdot L)$ 。