1. 项目概述PATProgramming Ability Test是浙江大学计算机程序设计能力考试其中Top Level题目难度最高主要考察算法设计能力和工程实现水平。1001题Battle Over Cities - Hard Version是一道经典的图论问题要求考生在给定城市和道路的连通图中计算摧毁某个城市后重建道路的最小成本。这道题在PAT系统中分值35分属于甲级考试中的压轴题型。我最近用Java完整实现了这个题目并在PAT官方评测系统中获得了满分。作为一道经典的连通图问题它融合了最小生成树算法、图的遍历和贪心策略等多个知识点非常值得深入剖析。2. 问题分析与建模2.1 题目描述解析题目给定N个城市和M条双向道路每条道路有修建成本。当某个城市被摧毁后所有与之相连的道路都会失效。要求找出使得剩余城市保持连通所需要重建道路的最小总成本。如果无法保持连通则输出对应标识。输入格式第一行N(≤500)和M(≤N(N-1)/2)接下来M行城市1 城市2 成本 状态1表示完好0表示已毁最后一行被摧毁的城市K2.2 核心问题抽象这实际上是一个带权无向图的连通性问题可以抽象为从原图中删除指定顶点及其所有邻边检查剩余图的连通性若连通计算使其连通的最小修复成本选择已毁道路修复若不连通返回特定标识2.3 算法选择依据针对这个问题我们需要组合使用以下算法DFS/BFS用于检查图的连通性Kruskal/Prim用于计算最小生成树修复成本最小化并查集(Union-Find)高效处理连通分量合并我最终选择DFSKruskal的组合方案因为DFS实现简单适合500节点规模的图Kruskal算法可以直接利用题目中已给出的边集并查集能高效支持Kruskal算法的实现3. Java实现详解3.1 数据结构设计class Edge implements ComparableEdge { int from, to, cost; boolean isActive; public Edge(int f, int t, int c, boolean a) { this.from f; this.to t; this.cost c; this.isActive a; } Override public int compareTo(Edge other) { return this.cost - other.cost; } } class Solution { private ListListInteger graph; private ListEdge edges; private int[] parent; // ...其他成员变量 }3.2 核心算法实现3.2.1 连通性检查(DFS)private boolean isConnected(int n, int destroyed) { boolean[] visited new boolean[n1]; int start (destroyed 1) ? 2 : 1; dfs(start, destroyed, visited); for(int i1; in; i) { if(i ! destroyed !visited[i]) return false; } return true; } private void dfs(int node, int destroyed, boolean[] visited) { if(node destroyed || visited[node]) return; visited[node] true; for(int neighbor : graph.get(node)) { if(neighbor ! destroyed) { dfs(neighbor, destroyed, visited); } } }3.2.2 Kruskal算法实现private int kruskal(int n, int destroyed) { initUnionFind(n); int res 0, count 0; // 只考虑被摧毁的道路 ListEdge candidates edges.stream() .filter(e - !e.isActive e.from ! destroyed e.to ! destroyed) .sorted() .collect(Collectors.toList()); for(Edge e : candidates) { if(find(e.from) ! find(e.to)) { union(e.from, e.to); res e.cost; if(count n-2) break; // n-1个城市需要n-2条边 } } return (count n-2) ? res : Integer.MAX_VALUE; }3.3 完整解决方案public int battleOverCities(int n, int m, int[][] roads, int destroyed) { // 初始化图结构 graph new ArrayList(); for(int i0; in; i) graph.add(new ArrayList()); edges new ArrayList(); // 构建邻接表和边集 for(int[] r : roads) { int u r[0], v r[1], cost r[2]; boolean active r[3] 1; graph.get(u).add(v); graph.get(v).add(u); edges.add(new Edge(u, v, cost, active)); } // 检查连通性 if(!isConnected(n, destroyed)) return -1; // 计算最小修复成本 int minCost kruskal(n, destroyed); return minCost Integer.MAX_VALUE ? -1 : minCost; }4. 优化与性能分析4.1 时间复杂度优化DFS连通性检查O(NM)对于N≤500完全可接受Kruskal算法O(MlogM)排序 O(Mα(N))并查集操作总体复杂度O(MlogM) 主导完全满足题目要求4.2 空间复杂度优化邻接表存储图O(NM)边集存储O(M)并查集O(N)总空间O(NM)非常高效4.3 Java特定优化技巧使用ArrayList而非数组存储边集方便后续的流式过滤操作提前过滤掉与被摧毁城市相关的边减少后续处理量使用Java 8 Stream API简化代码逻辑实现Comparable接口使边可排序5. 常见问题与调试技巧5.1 边界条件处理城市编号题目中城市编号从1开始注意数组越界单城市情况当N1时摧毁后无需修复全连接检查DFS/BFS必须遍历所有未被摧毁的城市5.2 典型错误案例并查集未初始化每次Kruskal前必须重置parent数组边排序错误确保Edge正确实现Comparable接口连通分量计数错误n个城市需要n-1条边但摧毁1个后只需n-2条5.3 调试建议先小规模测试N3,4可视化图的连接关系打印中间结果选中的边、并查集状态对比手动计算的最小生成树6. 算法扩展与变种6.1 问题变种思考多城市摧毁同时摧毁多个城市的情况动态查询多次查询不同城市被摧毁的结果部分修复允许修复部分已毁道路但需满足连通性6.2 替代算法方案Prim算法适合稠密图可使用优先队列实现Borůvka算法并行计算各连通分量的最小边逆向思维计算需要保留的最小边集6.3 实际应用场景网络容灾规划交通枢纽应急方案电力网络冗余设计7. PAT备考建议7.1 题目训练策略先掌握基础图论算法DFS/BFS/最短路径熟练实现并查集及其优化理解最小生成树的各种应用场景大量练习甲级真题中的图论题7.2 Java编程技巧合理使用集合框架ArrayList/HashSet掌握Comparator的自定义排序善用Stream API简化代码注意输入输出效率使用BufferedReader7.3 时间管理建议先确保正确性再优化预留20%时间检查边界条件使用模块化编程如分离连通性检查和MST计算准备常用算法模板如并查集、快速排序这道题的难点在于将实际问题抽象为图论模型并组合运用多种算法。我在实现过程中最大的收获是认识到并查集在图算法中的强大作用。对于PAT考生来说建议从简单图论题开始逐步过渡到这种综合题型同时要注重代码的模块化和可读性。