1003 Universal Travel Sites

1003 Universal Travel Sites📘 题目原文（英文）🌏 题目翻译（中文）💡 解题思路问题本质算法选择步骤分解关键点💻 带逐句注释的代码📘 题目原文（英文）1003 Universal Travel SitesScore: 35Author: CHEN, YueUnit: Zhejiang UniversityAfter finishing her tour around the Earth, CYLL is now planning a universal travel sites development project. After a careful investigation, she has a list of capacities of all the satellite transportation stations in hand. To estimate a budget, she must know the minimum capacity that a planet station must have to guarantee that every space vessel can dock and download its passengers on arrival.Input Specification:Each input file contains one test case. For each case, the first line contains the names of the source and the destination planets, and a positive integer N (≤500). Then N lines follow, each in the format:source[i] destination[i] capacity[i]wheresource[i]anddestination[i]are the names of the satellites and the two involved planets, andcapacity[i] 0is the maximum number of passengers that can be transported at one pass fromsource[i]todestination[i]. Each name is a string of 3 uppercase characters chosen from {A-Z}, e.g., ZJU.Note that the satellite transportation stations have no accommodation facilities for the passengers. Therefore none of the passengers can stay. Such a station will not allow arrivals of space vessels that contain more than its own capacity. It is guaranteed that the list contains neither the routes to the source planet nor that from the destination planet.Output Specification:For each test case, just print in one line the minimum capacity that a planet station must have to guarantee that every space vessel can dock and download its passengers on arrival.Sample Input:EAR MAR 11 EAR AAA 300 EAR BBB 400 AAA BBB 100 AAA CCC 400 AAA MAR 300 BBB DDD 400 AAA DDD 400 DDD AAA 100 CCC MAR 400 DDD CCC 200 DDD MAR 300Sample Output:700🌏 题目翻译（中文）题目：1003 通用旅行站点在完成地球之旅后，CYLL 正在规划一个通用旅行站点开发项目。经过仔细调查，她手头有一份所有卫星运输站容量的列表。为了估算预算，她必须知道一个行星站必须拥有的最小容量，以保证每一艘太空船都能在到达时停靠并让乘客下船。输入格式：每个输入文件包含一个测试用例。对于每个测试用例，第一行包含源行星和目标行星的名称，以及一个正整数 N（≤500）。接着是 N 行，每行格式为：source[i] destination[i] capacity[i]，其中source[i]和destination[i]是卫星和所涉及的两个行星的名称，capacity[i] 0是一次运输中从source[i]到destination[i]的最大乘客数量。每个名称是由 {A-Z} 中选取的 3 个大写字母组成的字符串，例如 ZJU。注意：卫星运输站没有乘客住宿设施。因此，任何乘客都不能滞留。这样的站点不允许任何超过其自身容量的太空船到达。保证列表中不包含从源行星出发的路线，也不包含到达目标行星的路线。输出格式：对于每个测试用例，输出一行，表示一个行星站必须拥有的最小容量，以保证每一艘太空船都能在到达时停靠并让乘客下船。💡 解题思路问题本质这是一个**最大流（Maximum Flow）**问题。把每个行星和卫星看作图中的一个节点。把每条运输路线看作一条有向边，边的权值（容量）表示该路线一次能运输的最大乘客数。题目要求的是：从源行星到目标行星，在不超过任何边容量的情况下，单位时间内能运输的最大乘客数量。这个最大流的值，就是行星站必须拥有的最小容量（因为行星站需要容纳所有到达的乘客，而最大流就是可能同时到达的最大乘客数）。算法选择使用Dinic 算法求解最大流，时间复杂度 O(E√V) 到 O(V²E)，在本题 N ≤ 500 的规模下足够快。步骤分解读入输入：源行星名、目标行星名、边数 N。节点映射：用mapstring, int将每个行星/卫星名称映射为整数 ID，方便建图。建图：使用 Dinic 算法中的邻接表结构，添加有向边（包括反向边，容量为 0）。计算最大流：调用max_flow(source_id, dest_id)。输出结果：最大流的值即为答案。关键点反向边的作用：提供“反悔”机制，允许算法调整之前的流量分配。BFS 分层：确保每次增广都沿着最短路径（边数最少）进行。当前弧优化：避免在 DFS 中重复检查已经饱和的边。💻 带逐句注释的代码#includeiostream#includevector#includequeue#includemap#includestring#includeclimits// 用于 INT_MAXusingnamespacestd;// 边的结构体structEdge{intto;// 边的终点（目标节点ID）intrev;// 反向边在邻接表中的索引intcapacity;// 当前剩余容量Edge(intt,intr,intc):to(t),rev(r)