Any questions?
Reply Back New Topic
View Topic

题解 4288: 最小生成树计数


本文同步发售于 洛谷博客

考虑性质【具有相同权值的边不会超过 条】

从一般套路来看, 可能涉及指数级算法。



所以我们用猜复杂度的方法知道了实际复杂度与 有关

考虑 一般的做法:按位枚举。

于是就可以口胡出一种做法,证明在后

做法:
「一」对于 mst 上有的边 的权值(设权值为 ,且这样的边在 原图 上有 条),先连接 mst权值非 的边(尤指并查集合并操作)
「二」对于剩下的 原图上的权值为 的边,枚举子集(即:二进制从 枚举)
「三」对于枚举得到的一种子集,首先要保证若这些子集中的边全部加入,得到的图的边数为

形式化的说,我们要保证 mst 上权值非 的边的条数 +

「四」接下来我们要保证若这些子集中的边全部加入,得到的是一棵(而不是非连通图)。这是,我们可以通过类似 kruskal 的方式利用并查集维护点联通关系。只要有任意一条边在连接时导致了环的形成(即:这条边的两个端点早已联通)则这种子集不构成对答案的贡献

注意,由于并查集的断边操作十分困难,而且若实现将只能按秩合并而不能路径压缩,所以我们在枚举子集之前fa 数组进行备份,这样可以快速地将 fa 数组还原到对这种子集检验之前的情况

证明:关键点在于证明“在所有最小生成树中,权值相等的边出现的次数相等”

现在我们考虑一颗 mst 中的两条边 连接 ,权值为 连接 ,权值为 。根据 mst 性质易知 中必定有两点可以不经过 到达,不妨设为

P4208-sol.PNG

前提 与图上三个蓝框代表的点集合构成一颗 mst
假设 1 有两条不属于 mst 的边 满足其权值均不等于 的权值
假设 2 与图上三个蓝框代表的点集合能构成一颗 mst

不妨设

  1. 如果有 ,可知在 kruskal 先于 访问。而 既然能满足假设 2,则 一定会被加入到 mst 中,与假设 1矛盾

  2. 如果有 ,由 前提假设 2 可知 ,所以易得 。此时在 kruskal 先于 访问。而 既然能满足假设 2,则 一定会被加入到 mst 中(且 将不会被加入到 mst 中),则可以得出一颗 mst ,其权值小于原 mst,矛盾。

现在已经可以得出这题的全部解法。

时间复杂度( 为“具有相同权值的边”的最多个数):

  • 枚举所有 mst 上有的边 的权值:

  • 对于 原图上的权值为 的边 枚举子集

  • 检验方案正确性 :

总时间复杂度:

代码:见我的 gitee 仓库

View Replies

Replied by Tanbowen 4 months ago 赞:2

ORZORZORZ