贺翔

分类

最小生成树(4)

/ 注册

全部文章（共4篇）

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

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

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

2020-04-29

0 710

洛谷题单<最小生成树> 无线通讯网

水题直接kruskal 加边数 == p - s 返回边长即可代码如下 #include<bits/stdc++.h> using namespace std; const int N = 510; int s, p; struct edge{ int a, b; ...

最小生成树 kruskal

2020-04-29

1 693

洛谷题单 <最小生成树> building roads

洛谷题单<最小生成树> 2krukal 的应用题目告诉原有M条边即修改M次并查集；考察对kruskal并查集的理解。代码如下 #include<bits/stdc++.h> using namespace std; typedef long long ll; const ...

最小生成树 kruskal

2020-04-29

0 762

洛谷题单最小生成树1

洛谷题单<最小生成树> 直接上代码 #include<bits/stdc++.h> using namespace std;//prim kruskal 都可以做； const int N = 5010, M = 200010; struct edge{ int...

最小生成树模板 kruskal

2020-04-29

0 664