最小生成树文章列表

[luoguP1783] 海滩防御（二分 || 最短路 || 最小生成树）

传送门 因为答案满足单调性，所以看到这个题，第一反应是二分，但是总是WA，也没有超时。 看了题解，，，，，， 这题刚开始很多人会想到二分，二分答案，然后看看是否能绕过所有信号塔，但是，这样写明显超时，...二分,并查集,最短路,kruskal,dijkstra

[BZOJ2594] [Wc2006]水管局长数据加强版（LCT + kruskal + 离线）

传送门 WC这个题真是丧心病狂啊，就是想学习一下怎么处理边权，给我来了这么一个破题！ ORZ hzwer 临摹黄学长代码233 但还是复杂的一匹 理一下思路吧 题目大意：给定一个无向图，多次删除图中的...LCT,kruskal,最小生成树

[POJ1797] Heavy Transportation（最大生成树 || 最短路变形）

传送门 1.最大生成树 可以求出最大生成树，其中权值最小的边即为答案。 2.最短路 只需改变spfa里面的松弛操作就可以求出答案。 ——代码 1 #include queue 2 #include c...最小生成树,最短路,spfa

【模板】prim的heap优化

简单的代码。。 时间复杂度为O((n + m)logn) 大部分情况下还是跑不过kruskal的，慎用。 1 #include cstdio 2 #include queue 3 #include c...模板,最小生成树,prim,堆,stl

公路修建（Prim）

洛谷传送门 这道水题告诉了我，堆优化的prim有时还不如朴素prim快。。。 居然记错时间复杂度了，我也真是菜。 1 #include cstdio 2 #include queue 3 #inclu...prim,最小生成树

NOIP2013D1T3货车运输（最大生成树+倍增lca）

传送门 这道题，先用kruskal求一遍图中的最大生成树。 然后，倍增求lca，求lca的同时求出边权的最小值。 #include cstring#include cstdio#include alg...最小生成树,lca,倍增

共1页/6条

---

香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化