zcmimi's blog

arrow_back最小生成树共5篇文章

avatar
zc
2020-09-14 16:15:00
查看原题

点击跳转

题意: 给一颗树,每条边权值可以修改为x,使得修改后这条边可以在最小生成树上,问x最大可以是多少?

首先求出最小生成树(以下的树指最小生成树)

修改一条边时,若不是最小生成树上的边,则为树上该边两端节点之间的最大值

若是树上的边,那么就是该边子树中找出一些非树边(使它们最大值尽可能小)连接除子树部分的点,答案为该边权值

看上去不是很好处理

我们将非树边按权值从小到大排序,从下往上合并,用并查集维护即可

每次遇到非树边x,y时,就更新并合并x\to \text{lca}_{x,y},y\to \text{lca}_{x,y},从下往上跳时,并查集可以跳过已经打过标记的边

详见代码

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

思路很妙

注意m-n \le 20

也就是说最多只有21条非树边

我们可以先跑一遍kruskal,然后按套路建树,两点之间的距离就是d_x+d_y-2\times lca(x,y)

接着剩下最多21条边(42个节点),再跑最多42次最短路就可以处理出加上非树边的结果了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

link\ cut\ tree维护最小生成树

直接在线很难,我们可以离线加边

先把所有边(后来断掉的不算)跑一遍最小生成树

接着每次加边,设加xy,边长为w

先求出xy路径上最长的边

如果比要加的边长,则删掉这条边,加上新边

这样就可以lct维护最小生成树

因为lct不能直接维护点,所以我们可以把边看成点

x\rightarrow边\rightarrow y

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

仔细考虑一下,最终能够形成最小权值的生成树的情况一定是把S都用在减小某条边的费用

  1. 如果那条边在最小生成树上,那么直接处理即可

  2. 如果在外面,设这条边为x \rightarrow y,我们求出最小生成树上xy上最大的一条边,删掉这条边

枚举删掉哪条边,然后执行上面的操作就可以了

记得开long\ long,rmq的数组开大点

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

1/1
Search
search