题目描述DRM Inc.\texttt{DRM Inc.}DRM Inc.是一家生产数字道路地图的公司。一张数字地图由一组地点和一组连接地点的街道组成。街道是无向的即双向街道。地点aaa到地点bbb的道路是一个地点序列⟨u0,u1,…,un⟩\langle u_0, u_1, \ldots, u_n \rangle⟨u0,u1,…,un⟩满足au0a u_0au0bunb u_nbun并且对于0≤in0 \leq i n0≤inuiu_iui和ui1u_{i1}ui1之间有一条街道。地图的定义是逐步完成的新版本的地图是在已有地图的基础上添加细节构建而成。新地图必须与旧地图一致即新地图必须比旧地图更详细具体要求如下新地图至少包含旧地图中的所有地点对于旧地图中连接地点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题目分析本题的核心是判断两张地图之间的“更详细”关系。这本质上是一个图论包含关系的判定问题。将地图建模为无向图每个地点是一个节点每条街道是一条无向边。那么“更详细”的定义转化为节点集包含新图的节点集合必须包含旧图的所有节点。路径存在且中间节点为新对于旧图的每条边(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)如果在新地图中存在直接边(u,v)(u, v)(u,v)则直接通过路径长度为111无中间节点。否则执行广度优先搜索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(V2E2)O(V_2 E_2)O(V2E2)。条件 1 检查O(V1)O(V_1)O(V1)。条件 2 检查对每条旧边进行BFS\texttt{BFS}BFS每次BFS\texttt{BFS}BFS的复杂度为O(V2E2)O(V_2 E_2)O(V2E2)。总复杂度O(E1⋅(V2E2))O(E_1 \cdot (V_2 E_2))O(E1⋅(V2E2))。在最坏情况下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//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 读取地图返回 (id, 地点集合, 街道集合)tuplestring,unordered_setstring,setpairstring,stringreadMap(){string id;cinid;unordered_setstringplaces;setpairstring,stringstreets;string a,b;while(cina){if(a*){cinb;// 第二个 *cinb;// 第三个 *break;}cinb;places.insert(a);places.insert(b);if(ab)swap(a,b);streets.insert({a,b});}return{id,places,streets};}intmain(){while(true){auto[id1,oldPlaces,oldStreets]readMap();if(id1END)break;auto[id2,newPlaces,newStreets]readMap();// 条件1新地点必须包含所有旧地点booloktrue;for(conststringp:oldPlaces)if(newPlaces.find(p)newPlaces.end()){okfalse;break;}if(!ok){coutNO: id2 is not a more detailed version of id1\n;continue;}// 构建新地图的邻接表unordered_mapstring,vectorstringnewAdj;for(autoe:newStreets){newAdj[e.first].push_back(e.second);newAdj[e.second].push_back(e.first);}// 条件2检查旧地图的每条街道for(autoe:oldStreets){string ue.first,ve.second;// BFS 从 u 到 v只允许经过新地点但 u 和 v 本身允许是旧地点unordered_setstringvisited;queuestringq;q.push(u);visited.insert(u);boolreachablefalse;while(!q.empty()){string curq.front();q.pop();if(curv){reachabletrue;break;}for(string nxt:newAdj[cur]){if(visited.count(nxt))continue;// 中间节点必须是新地点不在 oldPlaces 中或者就是终点 vif(nxt!voldPlaces.count(nxt))continue;visited.insert(nxt);q.push(nxt);}}if(!reachable){okfalse;break;}}if(ok)coutYES: id2 is a more detailed version of id1\n;elsecoutNO: id2 is not a more detailed version of id1\n;}return0;}总结本题是一道典型的图论包含关系判定问题核心在于正确理解“更详细”的两个条件并分别进行验证节点包含简单的哈希集合包含判断。受限路径存在需要在新图的子图上进行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可能在新图中孤立的情况即没有邻接边。输入格式中街道顺序可能乱序需要统一规范存储如字典序。本题适合用来训练图论建模能力和对复杂条件的实现能力。