题目链接 星际数据下载 题目描述 在一个有向图中，每个节点有权值（数据量）。从一个指定的起点 S 出发，沿着有向边行走，可以重复经过节点和边，但每个节点的权值只能收集一次。当到达任意一个指定的终点时，任务结束。目标是找到一条从起点到任意终点的路径，使得路径上所有不同节点的权值之和最大。 解题思路 本题是上一题“魔法迷宫探宝”的变种。核心思想依然是强连通分量 (SCC) 缩点，因为一旦进入一个 SCC，就可以访问该 SCC 内的所有节点。主要区别在于本题有固定的起点和一组终点。 算法步骤如下：   SCC 缩点：  使用 Tarjan 算法找到原图中的所有强连通分量。 将每个 SCC 视为一个“...

题目链接 魔法迷宫探宝 题目描述 在一个有向图中，每个节点有一定权值（宝石价值）。可以从任意节点出发，沿有向边行走，可以重复经过节点和边，但每个节点的权值只能被计算一次。目标是找到一条路径，使得路径上所有不同节点的权值之和最大。 解题思路 这个问题的核心在于处理“可以重复经过节点”这一条件。如果图中的一些节点可以相互到达，那么只要我们进入了这个区域，就可以访问该区域内的所有节点，从而收集全部的宝石。这个“可以相互到达的”区域，在图论中被称为强连通分量 (Strongly Connected Component, SCC)。 因此，我们可以将问题分解为以下几个步骤：   缩点 (Graph Co...

题目链接 核心信任者 题目描述 在一家有  名员工的公司里，存在  条单向的直接信任关系 u -> v (u 信任 v)。这种信任关系具有传递性，即如果 A 信任 B 且 B 信任 C，则 A 也信任 C。 如果一名员工被所有（包括他自己）员工信任，那么他被称为“核心信任者”。你需要计算公司里核心信任者的数量。 解题思路 这是一个典型的图论问题。我们可以将员工和信任关系抽象为一个有向图，然后通过分析图的结构来找出核心信任者。 1. 图的建模  节点 (Nodes)：每位员工是一个节点。 边 (Edges)：每条信任关系 u -> v 是一条从 u 指向 v 的有向边。 传递性：A ...

题目链接 任务分配 题目描述 在一个工人和任务的分配场景中，每个工人 W 初始负责任务 T。此外还有一些“跨职能”的分配关系。一个初始分配 W -> T 被认为是“不稳定”的，如果去掉这条分配后，仍然能让所有工人完成所有任务（即存在一个完美匹配）。否则，该分配是“稳定”的。需要判断每个初始分配的稳定性。 解题思路 这是一个关于二分图完美匹配中边的性质判断问题。如果逐一删除每条边并重新计算最大匹配，对于  高达  的数据规模，复杂度过高。我们需要一种更高效的算法。这个问题的标准解法是结合完美匹配和强连通分量 (SCC)。 核心思想   二分图建模：  工人和任务构成二分图的两个顶点集。 “...

题目链接 同义词替换 题目描述 给定一篇由  个单词组成的作文和  条同义词替换规则。每条规则 u -> v 表示单词 u 可以被替换为 v（单向，大小写不敏感）。这种替换具有传递性，即若 a -> b 且 b -> c，则 a 可以被替换为 c。 目标是对作文进行任意次数的替换，以得到一篇新的作文，满足：  首要目标：新作文中字母 'r' 的出现次数（大小写不敏感）最少。 次要目标：在满足上一目标的前提下，新作文的总长度（所有单词长度之和）最短。  你需要输出这两个值：最少的 'r' 出现次数和对应的最短总长度。 解题思路 这是一个图论问题。我们可以将单词和替换规则模型化为...

题目链接 激活码分发 题目描述 在一个员工网络中，一些员工愿意将激活码分享给另一些员工。这种分享关系是具有传递性的。求最少需要购买多少个激活码，才能保证每位员工都拥有激活码。 解题思路 这是一个经典的图论问题，可以通过寻找图中的强连通分量 (Strongly Connected Components, SCC) 来解决。 图论建模  节点：将每位员工看作图中的一个节点。 有向边：如果员工 u 愿意将激活码分享给员工 v，我们就建立一条从 u 到 v 的有向边 u -> v。  强连通分量 (SCC)  定义：在有向图中，如果一个顶点子集中，任意两个顶点都互相可达，则这个子集被称为一个强连...

题目链接 【模板】拓扑排序 题目描述 给定一个包含  个顶点和  条边的有向图。你需要输出该图的一个拓扑序（Topological Order）。  拓扑序：一个有向无环图（DAG）中所有顶点的线性排序，该排序满足对于图中任意一条从顶点  到顶点  的有向边 ，在排序中  都出现在  之前。 如果存在多个合法的拓扑序，输出任意一种即可。 如果图中存在有向环，导致无法进行拓扑排序，则输出 -1。  解题思路 本题是拓扑排序的模板题。拓扑排序是处理有向无环图（DAG）问题的核心算法之一。最常用的实现方法是基于卡恩算法（Kahn's Algorithm），该算法利用了顶点的入度（In-degree）...

题目链接 最小生成树的最长边 题目描述 给定一个带权无向连通图，求其任意一棵最小生成树 (MST) 中，权重最大的边的权重值。 解题思路 这个问题的核心是求解最小生成树，并找出其中的最长边。使用 Kruskal 算法 可以非常自然地解决这个问题。 Kruskal 算法 Kruskal 算法是一种基于贪心策略的最小生成树算法。其基本思想是：  将图中所有的边按照权重从小到大进行排序。 初始化一个空的边集合，用于构成最小生成树。 依次遍历排序后的边。对于当前遍历到的边，如果将它加入到集合中不会与已有的边形成环，则将这条边加入集合。 重复步骤3，直到集合中有  条边为止（ 是顶点数）。  为了高效地...

题目链接 最高分不下降路径 题目描述 在一张带点权的无向图中，寻找一条从顶点1到顶点N的简单路径，要求路径上节点的权值是广义单调递增（非递减）的。在所有满足条件的路径中，找出一条路径，使其包含的不同权值数量最多。输出这个最多的数量。如果不存在这样的路径，则得分为0。 解题思路 这是一个在图上寻找满足特定条件的、从固定起点到固定终点的最长路径问题，可以利用动态规划来解决。关键在于“权值非递减”和“1->N”这两个约束。 DP on DAG   模型转换： “路径上节点权值非递减”的限制，意味着我们只能从一个节点 u 移动到其邻居 v 当且仅当 weight[u] <= weight[...

题目链接 邮递员送信 题目描述 在一个有  个路口和  条单向道路的城市里，1 号路口是邮局。邮递员需要向 2 号到  号路口的每一个路口都投递一件包裹。 投递规则如下：  邮递员一次只能携带一件包裹。 每次都必须从 1 号路口（邮局）出发，前往目的地路口。 送达后，必须返回 1 号路口（邮局），才能取下一件包裹。  你需要计算，邮递员完成所有  件包裹的投递并最终回到邮局，所需的最短总时间。 解题思路 这道题的核心是计算  次独立的投递任务的总耗时。 1. 分解问题 对于每一个目的地 （从 2 到 ），邮递员都需要完成一次往返行程：  从邮局（1号路口）出发，到达目的地 。 从目的地  出发...

题目链接 电话线 题目描述 给定一个包含  个电话杆和  段可用电缆的图。每段电缆连接两个电话杆并有相应的长度。 目标是连接电话杆 1 (公共电话网) 和电话杆  (庄园)。电话公司免费提供最多  段电缆。如果选择的连接路径需要超过  段电缆，则需要自行支付超出的部分。支付的费用等于所需购买的电缆中最长的那一段的长度。 你需要计算连接 1 号和  号电话杆所需的最小费用。如果无法连接，则输出 -1。 解题思路 这是一个典型的**“最小化最大值”问题，是二分答案**的经典应用场景。 我们要求解的是“最小的费用”，这个费用实际上是路径上某条边的长度。我们可以对这个“费用”进行二分查找。 1. 二分...

题目链接 新年好 题目描述 在一个带权无向图中，从1号点出发，需要访问5个指定的亲戚所在的节点。拜访顺序任意，求完成所有拜访所需的最短总时间。 解题思路 这个问题可以看作是一个简化版的旅行商问题 (Traveling Salesman Problem, TSP)。由于需要访问的节点数量非常少（只有5个亲戚），我们可以通过暴力枚举所有可能的拜访顺序来找到最优解。 整个解题过程可以分为两个主要步骤： 1. 预处理：计算关键点之间的最短路径 首先，我们需要知道所有“关键点”之间两两的最短距离。这里的关键点包括家（1号节点）和5个亲戚所在的节点，共6个点。 原图可能包含很多与拜访路线无关的节点和边，直...

题目链接 最优乘车 题目描述 给定一个城市的公交网络，包含若干个站点和若干条单向公交线路。每条线路都按顺序经过一系列站点。乘客可以在任意站点换乘。求从1号站到N号站的最少换乘次数。 解题思路 这是一个典型的图论建模和最短路径问题。问题的关键在于如何定义图的节点和边，以使“最少换乘次数”这个目标能够通过标准算法求解。 图的建模 我们可以将问题转化为求解一个无权图的单源最短路径。   转化目标：最少换乘次数等价于乘坐最少的公交线路数。如果乘坐了  条线路，那么换乘次数就是 。因此，我们的目标是找到一条使用最少公交线路从起点到终点的路径。   节点 (Vertices)：图中的节点可以直接对应为公交...

题目链接 游游出游 题目描述 给定一个包含  座城市和  条双向道路的图。每条道路连接两个城市，并具有最大承重和长度两个属性。 你需要计算出一辆车从城市 1 前往城市  的最大可能重量，前提是车辆的总行驶距离不能超过一个给定的上限 。车辆的重量必须小于等于其所经过的每一条道路的最大承重。 如果无法在距离限制内从城市 1 到达城市 ，输出 -1。 解题思路 这道题要求在满足一个约束（总长度 ）的前提下，最大化另一个值（车辆重量）。这是一个典型的最大化最小值或最优化问题，非常适合使用二分答案的技巧来解决。 1. 二分答案 我们可以对车辆的重量 进行二分查找。问题的关键在于，如果一个重量为  的车可...