图论 - 大矩学习资料

牛客网16445题：Dijkstra算法解决共享单车问题

2周前 (08-24)82

本文详解牛客网16445题的最优解法，提供带自行车切换功能的最短路径Dijkstra算法实现。通过状态拆分巧妙处理步行/骑行双模式，包含完整C++代码及逐行注释。内容涵盖题目解析、算法思路、复杂度分析和适用场景，特别适合准备算法面试的开发者。文章提供可运行的完整代码，帮助读者快速掌握状态机在图论算法...

2013年NOIP普及组车站分级（洛谷P1983）：拓扑排序算法实战指南

2周前 (08-22)91

本文详细解析了NOIP2013普及组车站分级问题的拓扑排序解法。通过构建车站间的有向图关系，采用Kahn算法实现拓扑排序，动态计算每个车站的最小级别。文章完整展示了C++实现代码，包含邻接表建图、入度统计和层级计算等关键步骤的详细注释。特别适合图论初学者学习如何将实际问题转化为拓扑排序问题，理解有向...

洛谷P1195题：最小生成树与Kruskal算法实践

3周前 (08-18)87

本文详细解析了如何运用Kruskal算法解决云朵连接问题，从问题分析、算法选择到代码实现步步深入，特别适合图论初学者。...

牛客网25438题：BFS算法解机器人移动范围问题

3周前 (08-17)99

本文详细解析牛客网25438题机器人移动范围问题，提供完整的BFS算法实现，包含数位和计算、坐标合法性判断等关键步骤讲解，帮助开发者掌握网格遍历类问题的通用解法。...

力扣2858题：从BFS到动态规划巧解有向图

4周前 (08-12)100

本文详细讲解了力扣2858题的解题思路，通过两次BFS遍历和巧妙的递推关系，高效计算了每个节点作为根时的最少边反转次数。文章包含完整的C++实现、算法解释和复杂度分析，适合图论初学者学习。...

洛谷P1073题（2009年NOIP提高组）：最优贸易问题解析——SPFA算法的巧妙应用

4周前 (08-10)92

一、问题背景最优贸易问题要求在一个有向图中找到一条路径，使得在这条路径上某点买入、后续某点卖出时能获得最大利润。这是典型的图论问题，考察了图的遍历和动态规划思想。二、算法选择使用SPFA(Shortest Path Faster Algorithm)算法，它是Bellman-Ford算法的优化版本，...