【2018SCUACM FurtherTraining 20 MST】

题目来源

A:UVA1395

B:UVA1151

C:UVA1664

D:HDU4081

E:UVA11354

F:CF160D

G:UVA10600

解题报告

A:先将边权按照递增排序,枚举边编号区间\([L,R]\),使用\(Kruskal\)算法求连通性,若可连通,则存在不超过\(W_R-W_L\)的生成树,在所有可连通的区间内取\(W_R-W_L\)最小值即可。

B:注意到\(q\)很小,所以我们可以枚举所有的套餐选择方案。在此之前,先生成一颗最小生成树,获得\(n-1\)条边,不在这\(n-1\)条边又不在套餐中的边不可能是答案,直接不管。所以对每种所有套餐选择方案,先计算套餐花费,并使用并查集将其连通,再枚举那\(n-1\)条原始最小生成树的边,选取一些构造新的最小生成树。在所有的这些新最小生成树中选择总权值最小的即可。

C:思路十分巧妙的一道题。我们可以把整个树划分为很多棵树,最初是\(n\)棵,每个结点都是一棵树,没有边。然后我们来慢慢加边让其逐渐连通。

首先把边按照长度从大到小排序,枚举每一条边并加入树中,由于边已经排过序,所以我们枚举的当前边一定是我们已经加入的边中最小的那条。考虑这条边连接的两点\(u,v\),设\(u\)和\(v\)两点所在的两棵树的中心点分别为\(A\)和\(B\),其大小分别为\(nSize[A]\)与\(nSize[B]\),容量分别为\(sum[A]\)与\(sum[B]\),则不难得到:

1.选A作为合并\(u,v\)后的中心点,新容量为:\(sum[A]+nSize[B]*e[i].len\),合并后\(nSize[A]=nSize[A]+nSize[B]\)

2.选B作为合并\(u,v\)后的中心点,新容量为:\(sum[B]+nSize[A]*e[i].len\),合并后\(nSize[B]=nSize[B]+nSize[A]\)

我们取两个方案中新容量更大的那个即可,比如选取方案\(1\),合并时做并查集将\(B\)连到\(A\)上即可,反之亦然。

最后扫一遍看哪个\(sum\)最大就选哪个。

D:考察最小瓶颈路的应用,使用\(LCA\)实现。先建\(MST\),之后枚举点,考虑在两点间建造魔法道路后形成一个环,显然删去环中最长边最划算,于是就转化成最小瓶颈路问题了。

E:多组询问,求最小瓶颈路的板子题,由于询问次数多,只能用\(LCA\)实现。

F:考虑\(Kruscal\)实现最小生成树时的做法:每次取出权值最小的一条边,看端点是否在同一集合中,不是就加入\(MST\)。

但是同时,权值与这条边一样小的边有一些就被排除掉了,实际上这些权值相同的边有可能都属于某棵\(MST\)。所以本题我们需要稍微变通一下,每次不是取出最小的那一条边,而是把权值相同且都是当前最小的边取出,如果端点不在同一集合中,则这些边按照\(Kruscal\)的规则都是可以选的,所以它们都至少是\(at\ least\ one\)。

那么如何判定\(any\)呢?也很简单,我们把权值相同的边取出后,如果端点不在同一集合,就将它加入到现在构建好的原图中。之后再跑一遍\(Tarjan\)求桥的算法,不过因为有重边,不能简单判断回不到父亲节点,而是需要记录走来的边,不沿着那条边走回去……若有\(dfn[now]<low[next]\),则\((now,next)\)之间的这条边就是桥,因为从\(next\)出发的边无论如何也回不到\(now\)(想想\(dfn\)和\(low\)的定义)。这些桥一定就是\(any\)了。跑完\(Tarjan\)之后记得缩点并去边。

 

G:最小生成树+次小生成树。根据题意不难得出\(S_1\)就是最小生成树权值和,\(S_2\)就是次小生成树权值和。求次小生成树只需要枚举不在最小生成树上的边,考虑加进去形成某一个环,删去环中最长边剩下的就是次小生成树,问题转化为求最小瓶颈路,数据大,必须\(LCA\)计算。

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*