贺翔

最小生成树

/ 注册

全部文章 / 最小生成树（共1篇）

洛谷题单<最小生成树> 货车运输

首先题目要求路径中的最大的最小值所以建立最大生成图那么唯一路径中的最小值就是题目答案又因为如果使用dfs/bfs求最小值的话时间复杂度是 O(n * q) 会超时所以使用lca（最近公共祖先）的思路求路径最小值。不了解的话建议在ACwing 上y总在提高课中有讲到（安利一波）或者阅读：http...

最小生成树最近公共祖先 kruskal lca

2020-04-29

0 711