BZOJ 3732: Network(Kruskal+LCA倍增)

Description

给你N个点的无向图 (1 <= N <= 15,000),记为:1…N。
图中有M条边 (1 <= M <= 30,000) ,第j条边的长度为: d_j ( 1 < = d_j < = 1,000,000,000).

现在有 K个询问 (1 < = K < = 20,000)。
每个询问的格式是:A B,表示询问从A点走到B点的所有路径中,最长的边最小值是多少?

Solution

Kruskal+LCA倍增

证明():对于每两个点u,v,如果存在在u,v路径上且比最小生成树小的边,在Kruskal枚举边数时其必定被考虑并加入,即对于所有点对的路径,Kruskal都尽量取最短了

注意:不能使用LCA Tarjan (无法logn查询最大值)

 

0 0 vote
Article Rating
Subscribe
提醒
guest
2 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Michael_Bryant
4 年 之前

博主太强了%%%
而且我也叫Michael 博客主题还是一样的(