题目链接：「NOI2020」翻修道路 题目难度：NOI/NOI+/CTSC\FCOLORBOX{#2C3E50}{#E9ECEF}{\COLOR{#2C3E50}NOI/NOI+/CTSC}NOI/NOI+/CTSC ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目大意 给一个无向图，要找一条从 S 到 T 的路径，使得删掉这条路径上的所有边之后，剩下的图仍然连通，并且路径总长度最小。如果找不到就输出 -1。 核心难点 一开始我以为直接跑最短路就完事了，结果发现删边之后图可能断掉。所以路径不能随便选，必须避开那些“删掉就会让图不连通”的边或点。 具体来说，有两类东西要避开： 1. 割点：如果路径经过割点，删掉路径后割点会把图分成几块，肯定不连通。 2. 分离边对：有些边单独删没事，但两条边同时删就会把图割开。这种边对不能同时出现在路径里。 算法流程 1. 找割点（TARJAN） 先跑一遍 Tarjan，把除了 S 和 T 之外的割点都标记成 bad。这些点不能出现在路径上。 2. 跑初始最短路（避开割点） 在避开 bad 点的图上跑 Dijkstra，得到一条从 S 到 T 的最短路，同时记录路径。 3. 分析非路径边，找“坏对” 路径上的点已经确定了，接下来要分析那些不在路径上的边。这些边可能把路径上的某些点“连起来”，如果两条这样的边同时被删，可能会把图割开。 这段有点像 Tarjan 的变种，目的是找出那些“如果同时删掉就会出问题”的边对，存到 bad_pair 里。 4. 并查集检查连通性 把路径上的边全部去掉，用并查集看看剩下的图是否连通。 5. 如果连通，直接输出最短路，否则跑带约束的最短路 如果去掉路径边后图还连通，那初始最短路就是答案。否则，需要用带状态的最短路，把 bad_pair 约束考虑进去。 这里 lim 数组是在 get_lim() 里算出来的，用来限制路径上的前进方向，避免走回头路导致重复经过某些边。 CODE 请大家踊跃质疑一下，我感觉哪里有点不严谨 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 100道题目竞赛 PART 1（WECE） > 空白团队池：66个 第1名：10个空白团队 第2名：7个空白团队 第3~5名：5个空白团队 第6~10名：2个空白团队 第11~20名：1个空白团队 幸运奖4个（500分以上）：1个空白团队 (暂定，2026年10月11日，可截图保存)