UVa 11336 DRM

题目描述

DRM Inc.\texttt{DRM Inc.}DRM Inc.是一家生产数字道路地图的公司。一张数字地图由一组地点和一组连接地点的街道组成。街道是无向的，即双向街道。

地点aaa到地点bbb的道路是一个地点序列⟨u0,u1,…,un⟩\langle u_0, u_1, \ldots, u_n \rangle⟨u0​,u1​,…,un​⟩，满足a=u0a = u_0a=u0​，b=unb = u_nb=un​，并且对于0≤i<n0 \leq i < n0≤i<n，uiu_iui​和ui+1u_{i+1}ui+1​之间有一条街道。

地图的定义是逐步完成的：新版本的地图是在已有地图的基础上添加细节构建而成。新地图必须与旧地图一致，即新地图必须比旧地图更详细，具体要求如下：

  • 新地图至少包含旧地图中的所有地点；
  • 对于旧地图中连接地点uuu和vvv的每条街道，在新地图中必须存在一条连接uuu和vvv的道路。这条道路的中间地点必须是新地点（即不在旧地图中的地点）。

DRM\texttt{DRM}DRM的构建过程包括比较相邻版本的地图，以确保它们之间的一致性。你需要帮助DRM\texttt{DRM}DRM判断一张地图是否比另一张地图更详细。

输入格式

每张地图由若干行表示：

  • 第一行包含地图的标识符。
  • 接下来的若干行（最后一行除外）每行包含两个地点的标识符，表示它们之间有一条街道。标识符之间用空格分隔。保证每条街道只被描述一次，但地点的顺序可能任意。此外，街道没有特定的顺序。
  • 最后一行是字符串* * *（星号、空格、星号、空格、星号）。

输入描述多个测试用例，每个用例由一对这样的地图表示。你需要判断每对中的第二张地图是否是第一张地图的更详细版本。

输入的结束由一行END\texttt{END}END表示。

输出格式

对于每个输入用例，按输入顺序输出。

对于每对地图<id1>和<id2>，如果<id2>比<id1>更详细，输出：

YES: <id2> is a more detailed version of <id1>

否则输出：

NO: <id2> is not a more detailed version of <id1>

样例

输入

COL1 Bogota Cali Bogota Barranquilla * * * COL2 Barranquilla Bogota Armenia Cali Barranquilla Armenia Bogota Cali Cali Barrranquilla * * * COL1 Bogota Cali Bogota Barranquilla * * * COL3 Bogota Armenia Armenia Cali Cali Medellin Medellin Barranquilla * * * END

输出

YES: COL2 is a more detailed version of COL1 NO: COL3 is not a more detailed version of COL1

题目分析

本题的核心是判断两张地图之间的“更详细”关系。这本质上是一个图论包含关系的判定问题。

将地图建模为无向图：每个地点是一个节点，每条街道是一条无向边。那么“更详细”的定义转化为：

  1. 节点集包含：新图的节点集合必须包含旧图的所有节点。
  2. 路径存在且中间节点为新：对于旧图的每条边(u,v)(u, v)(u,v)，在新图中必须存在一条从uuu到vvv的道路，且该道路除端点外，所有中间节点都不能出现在旧图中（即必须是新节点）。

第二个条件比单纯的“旧图的边在新图中存在路径”更强：它要求这条路径不能经过任何旧节点作为中间节点。这意味着，如果新图中有从uuu到vvv的路径，但该路径经过了某个旧节点www，那么这条路径是不合法的，因为www不是新地点。

一个关键的观察是：旧图中的边(u,v)(u, v)(u,v)本身可能在新图中直接存在（即(u,v)(u, v)(u,v)本身就是一条街道）。此时路径长度为111，没有中间节点，自动满足条件。

如果新图中不存在直接边，则需要通过一些新节点（即不在旧图中的节点）作为桥梁，连接uuu和vvv。

解题思路

数据结构选择

由于地点标识符是字符串，我们需要使用哈希结构来高效存储和查询。采用unordered_set\texttt{unordered\_set}unordered_set存储地点集合，采用set\texttt{set}set存储街道集合（并将端点按字典序排序以统一表示无向边）。

条件 1 的判断

遍历旧地图的所有地点，检查每个地点是否出现在新地图的地点集合中。一旦有一个缺失，即可判定为不满足。

条件 2 的判断

对于旧地图的每条边(u,v)(u, v)(u,v)，我们需要在新地图中进行一次受限的连通性查询：

  • 允许访问的节点包括：所有新地图中的节点。
  • 但中间节点（即路径上除起点uuu和终点vvv之外的节点）不能是旧地图中的节点。

换句话说，我们在新地图的图上，删除所有旧地图中的节点（保留uuu和vvv作为访问允许的例外），然后检查uuu和vvv是否连通。

注意：起点uuu和终点vvv本身可以是旧节点（因为它们就是旧地图中边的端点），但它们作为路径的端点不受到中间节点限制的约束。

实现方法

对于每条边(u,v)(u, v)(u,v)：

  1. 如果在新地图中存在直接边(u,v)(u, v)(u,v)，则直接通过（路径长度为111，无中间节点）。
  2. 否则，执行广度优先搜索（BFS\texttt{BFS}BFS）从uuu出发，只允许访问：
    • 新地图中存在的节点；
    • 除了vvv之外，不能访问旧地图中的节点。
      如果在搜索过程中遇到vvv，则说明存在合法路径。

注意：BFS\texttt{BFS}BFS的访问限制需要动态判断：当前节点为curcurcur，下一个节点为nxtnxtnxt。如果nxtnxtnxt等于vvv，则允许访问（因为它是终点）；否则，如果nxtnxtnxt是旧节点，则禁止访问。

时间复杂度分析

设：

  • V1V_1V1​为旧地图节点数，E1E_1E1​为旧地图边数；
  • V2V_2V2​为新地图节点数，E2E_2E2​为新地图边数；
  • 构建哈希表：O(V2+E2)O(V_2 + E_2)O(V2​+E2​)。
  • 条件 1 检查：O(V1)O(V_1)O(V1​)。
  • 条件 2 检查：对每条旧边进行BFS\texttt{BFS}BFS，每次BFS\texttt{BFS}BFS的复杂度为O(V2+E2)O(V_2 + E_2)O(V2​+E2​)。总复杂度O(E1⋅(V2+E2))O(E_1 \cdot (V_2 + E_2))O(E1​⋅(V2​+E2​))。

在最坏情况下，E1E_1E1​和E2E_2E2​都可能很大（节点数为nnn时边数可达O(n2)O(n^2)O(n2)量级）。但由于本题实际数据规模较小，该算法足以通过。

正确性说明

  • 条件 1 保证了新地图不会丢失旧地图中的任何地点。
  • 条件 2 保证了旧地图中的每条直接连接在更详细的地图中可以被一条“只通过新地点”的路径替代，这正符合题目中“中间地点必须是新地点”的要求。

因此，同时满足两个条件即为更详细版本。

代码实现

// DRM// UVa ID: 11336// Verdict: Accepted// Submission Date: 2026-06-13// UVa Run Time: 0.000s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 读取地图，返回 (id, 地点集合, 街道集合)tuple<string,unordered_set<string>,set<pair<string,string>>>readMap(){string id;cin>>id;unordered_set<string>places;set<pair<string,string>>streets;string a,b;while(cin>>a){if(a=="*"){cin>>b;// 第二个 *cin>>b;// 第三个 *break;}cin>>b;places.insert(a);places.insert(b);if(a>b)swap(a,b);streets.insert({a,b});}return{id,places,streets};}intmain(){while(true){auto[id1,oldPlaces,oldStreets]=readMap();if(id1=="END")break;auto[id2,newPlaces,newStreets]=readMap();// 条件1：新地点必须包含所有旧地点boolok=true;for(conststring&p:oldPlaces)if(newPlaces.find(p)==newPlaces.end()){ok=false;break;}if(!ok){cout<<"NO: "<<id2<<" is not a more detailed version of "<<id1<<"\n";continue;}// 构建新地图的邻接表unordered_map<string,vector<string>>newAdj;for(auto&e:newStreets){newAdj[e.first].push_back(e.second);newAdj[e.second].push_back(e.first);}// 条件2：检查旧地图的每条街道for(auto&e:oldStreets){string u=e.first,v=e.second;// BFS 从 u 到 v，只允许经过新地点（但 u 和 v 本身允许是旧地点）unordered_set<string>visited;queue<string>q;q.push(u);visited.insert(u);boolreachable=false;while(!q.empty()){string cur=q.front();q.pop();if(cur==v){reachable=true;break;}for(string nxt:newAdj[cur]){if(visited.count(nxt))continue;// 中间节点必须是新地点（不在 oldPlaces 中），或者就是终点 vif(nxt!=v&&oldPlaces.count(nxt))continue;visited.insert(nxt);q.push(nxt);}}if(!reachable){ok=false;break;}}if(ok)cout<<"YES: "<<id2<<" is a more detailed version of "<<id1<<"\n";elsecout<<"NO: "<<id2<<" is not a more detailed version of "<<id1<<"\n";}return0;}

总结

本题是一道典型的图论包含关系判定问题，核心在于正确理解“更详细”的两个条件，并分别进行验证：

  1. 节点包含：简单的哈希集合包含判断。
  2. 受限路径存在：需要在新图的子图上进行BFS\texttt{BFS}BFS，且该子图只包含“新节点”（加上边的端点作为例外）。

关键技巧：

  • 使用unordered_set\texttt{unordered\_set}unordered_set和set\texttt{set}set高效存储和查询节点与边。
  • 在BFS\texttt{BFS}BFS中动态决定哪些节点可以访问，而不是预先构建子图。
  • 注意边界情况：直接边存在时无需BFS\texttt{BFS}BFS，路径长度为111自动满足条件。

易错点：

  • 混淆旧节点和新节点的角色：路径的中间节点必须严格是新节点，但端点可以属于旧节点。
  • 忘记处理uuu或vvv可能在新图中孤立的情况（即没有邻接边）。
  • 输入格式中街道顺序可能乱序，需要统一规范存储（如字典序）。

本题适合用来训练图论建模能力和对复杂条件的实现能力。