「CEOI2014」城墙 题解 题目重述 给定一个 $n \times m$ 的网格，每个格子可能包含村庄（用 $1$ 表示）。需要建造一堵沿着网格线的闭合城墙，使得： • 从外部无法到达任何村庄 • 城墙从左上角开始并回到左上角 • 目标是最小化总建造花费 核心算法思想 这个问题可以转化为最小环问题，但需要保证环包围所有村庄。解法基于以下关键观察：

1. 对偶图转换 将网格的边转化为对偶图的节点，原问题转化为在对偶图中找到包含所有村庄的最小环。
2. 关键性质 • 最终的城墙必须包含从左上角到每个村庄的最短路 • 通过标记这些最短路径，确定哪些边必须被包含在最终解中
3. 算法步骤 步骤 1：初始最短路计算

Dijkstra(T, D1[0][0], 1); // 从左上角计算到所有点的最短路径

• 构建初始网格图，计算从 $(0,0)$ 到所有点的最短路径 • 记录路径信息用于后续标记 步骤 2：标记关键边

REP(i, 1, n) REP(j, 1, m) if (Village[i][j]) Mark(i - 1, j - 1), Mark(i - 1, j), Mark(i, j - 1), Mark(i, j);

• 对于每个村庄，标记其四个角点的最短路径 • 确定哪些网格边必须被城墙包含 步骤 3：构建对偶图 将原网格的边转化为四种状态的节点： • D1[i][j]: 水平边右侧状态 • D2[i][j]: 垂直边下方状态 • D3[i][j]: 水平边左侧状态 • D4[i][j]: 垂直边上方状态 步骤 4：最终最短路计算

Dijkstra(G, D1[0][0], 0); jyt << d[D4[0][0]] << '\n';

• 在构建的对偶图上计算从 D1[0][0] 到 D4[0][0] 的最短路 • 这个最短路对应原问题的最小花费城墙 算法复杂度 • 时间复杂度：$O(nm \log(nm))$，主要来自两次 Dijkstra 算法 • 空间复杂度：$O(nm)$，存储网格和图的邻接表 算法标签 主要标签： • 图论 ⭐⭐⭐⭐⭐ • 最短路 ⭐⭐⭐⭐⭐ • 对偶图 ⭐⭐⭐⭐ 次要标签： • Dijkstra 算法 ⭐⭐⭐⭐ • 网格图处理 ⭐⭐⭐⭐ • 最小环问题 ⭐⭐⭐ 技术标签： • 路径标记 ⭐⭐⭐ • 状态拆分 ⭐⭐⭐⭐ • 动态规划 ⭐⭐（隐含在图构建中） 关键创新点

1. 四状态节点设计：将每条网格边拆分为四个状态，表示城墙的不同穿越方式
2. 路径强制包含：通过标记村庄相关的最短路径，确保最终解包围所有村庄
3. 对偶图转换：将几何约束转化为图论问题，利用标准最短路算法求解 适用场景 这种解法适用于： • 网格上的包围问题 • 需要满足特定包含约束的最短路问题 • 几何约束的图论建模 该解法巧妙地将几何包围问题转化为标准的最短路问题，展现了图论建模在解决复杂约束问题中的强大能力。