华为 OD 机试：快递站点投递路径分析与解法

快递投放问题解析

在华为 OD 机试的双机位 C 卷中，这类图论结合业务场景的题目非常典型。核心在于如何根据给定的道路网络和检查站限制，判断包裹能否从起点到达终点。

题目理解

我们需要处理 N 个站点和 M 个包裹的投递任务。站点之间通过道路连接，但某些路段设有检查站，会拦截特定类型的货物。我们的目标是找出所有无法完成投递的包裹编号。

输入输出规范

• 输入：第一行包含两个整数 M 和 N（M 为包裹数，N 为道路数）。后续行描述包裹信息和道路连接。
• 输出：无法送达的包裹列表，按升序排列；若全部可达则输出 none。

注意：实际机考中，输入格式可能因具体年份略有差异，建议以现场示例为准，重点掌握图遍历逻辑。

解题思路

这道题本质上是一个有向图的连通性问题。我们可以将站点视为节点，道路视为边。对于每个包裹，我们需要判断其起点到终点是否存在一条不被检查站阻断的路径。

算法选择

由于需要多次查询不同包裹的可达性，且数据规模通常不大（N, M <= 100），使用 BFS（广度优先搜索） 或 DFS（深度优先搜索） 即可高效解决。每次针对一个包裹进行一次图遍历，复杂度约为 O(M * (V + E))，完全在可接受范围内。

关键点

1. 图构建：需要动态维护站点间的邻接关系。如果存在双向道路，需添加两条边。
2. 检查站逻辑：题目中提到'检查站禁止通行'，这通常意味着某些边带有属性（如禁止类型）。在代码实现时，可以将边标记为允许或禁止，遍历时跳过禁止边。
3. 结果排序：输出前务必对无法送达的包裹 ID 进行排序，这是容易丢分的细节。

代码实现

下面给出基于 Java 的实现方案。为了保持代码清晰，我们采用邻接表存储图结构。

import java.util.*;

public class Main {
    // 定义边的内部类，记录目标站点和是否被检查站拦截
    static class Edge {
        int to;
        boolean blocked;
        public Edge(int to, boolean blocked) {
            this.to = to;
            this.blocked = blocked;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        if (!scanner.hasNextInt()) return;
        
        int m = scanner.nextInt(); // 包裹数量
        int n = scanner.nextInt(); // 道路数量
        
        // 存储包裹信息：索引对应包裹 ID，值为 {起点，终点}
        List<Package> packages = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            String pkgName = scanner.next();
            String startNode = scanner.next();
            String endNode = scanner.next();
            packages.add(new Package(pkgName, startNode, endNode));
        }
        
        // 构建图：使用 Map 映射站点名称到 ID，方便处理字符串节点
        Map<String, Integer> nodeMap = new HashMap<>();
        List<List<Edge>> graph = new ArrayList<>();
        
        // 读取道路信息并建图
        // 假设道路输入格式为：起点 终点 是否拦截
        for (int i = 0; i < n; i++) {
            String u = scanner.next();
            String v = scanner.next();
            boolean isBlocked = scanner.nextBoolean(); // 假设输入包含拦截状态
            
            if (!nodeMap.containsKey(u)) nodeMap.put(u, nodeMap.size());
            if (!nodeMap.containsKey(v)) nodeMap.put(v, nodeMap.size());
            
            int uIdx = nodeMap.get(u);
            int vIdx = nodeMap.get(v);
            
            while (graph.size() <= Math.max(uIdx, vIdx)) graph.add(new ArrayList<>());
            
            graph.get(uIdx).add(new Edge(vIdx, isBlocked));
            graph.get(vIdx).add(new Edge(uIdx, isBlocked)); // 假设双向
        }
        
        List<String> failedPackages = new ArrayList<>();
        
        // 对每个包裹进行 BFS 检查
        for (Package pkg : packages) {
            if (!nodeMap.containsKey(pkg.start) || !nodeMap.containsKey(pkg.end)) {
                failedPackages.add(pkg.name);
                continue;
            }
            
            if (!bfs(nodeMap.get(pkg.start), nodeMap.get(pkg.end), graph)) {
                failedPackages.add(pkg.name);
            }
        }
        
        // 排序输出
        Collections.sort(failedPackages);
        if (failedPackages.isEmpty()) {
            System.out.println("none");
        } else {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < failedPackages.size(); i++) {
                sb.append(failedPackages.get(i));
                if (i < failedPackages.size() - 1) sb.append(" ");
            }
            System.out.println(sb.toString());
        }
    }
    
    // BFS 寻找路径
    private static boolean bfs(int start, int end, List<List<Edge>> graph) {
        if (start == end) return true;
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        
        queue.offer(start);
        visited.add(start);
        
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (Edge edge : graph.get(curr)) {
                if (!edge.blocked && !visited.contains(edge.to)) {
                    if (edge.to == end) return true;
                    visited.add(edge.to);
                    queue.offer(edge.to);
                }
            }
        }
        return false;
    }
    
    static class Package {
        String name, start, end;
        public Package(String name, String start, String end) {
            this.name = name;
            this.start = start;
            this.end = end;
        }
    }
}

调试与优化

在实际提交过程中，有几个坑需要注意：

1. 节点映射：题目中的站点是字符串，直接作为数组下标会越界，必须用 HashMap 做映射。
2. 边界情况：起点等于终点的情况，或者没有道路的情况，都要单独处理。
3. 输入解析：Scanner 在处理混合类型（String 和 Boolean）时，有时会因为换行符导致读取错误，建议统一使用 next() 读取字符串后自行转换。
4. 性能：虽然 N 很小，但如果测试用例极多，可以考虑预处理连通分量（Union-Find），不过对于单次查询 BFS 已经足够。

这类题目考察的是基础的数据结构应用能力。只要把图模型建对，剩下的就是标准的模板代码了。多做几道类似的图论题，手感自然就来了。