Any questions?
Reply Back New Topic
View Topic

最小生成树计数【题解】


这里讲一下做法和证明

做法

先做一遍kruskal,记录权值为x的边使用次数为sum[x],把图中所有边边按权值分成若干集合。

对于一张图的MST,每种不同方案中,树上某种权值的边数量是不变的(1)

那么可以对每种边权进行dfs,判断有多少种合法的组合方式,再乘法原理即可。

这个时候有些问题需要解决:

1.为什么(1)

2.如何保证在权值为x的集合中合法的方案在全局也合法?

那么,下面给出证明:
———————————————————————————————————————————————————————————————————————————————————————————————————————————————————————

证明

其实这两个可以一起解释

考虑kruskal的过程,先根据边权从小到大对边进行排序,再依次取出来每条边,判断两端点是否已在同一冰茶几,若是,则continue;否则,加入MST中并合并两端所在冰茶几。

好,那么对于权值相同的一些边,他们的被处理顺序必然是连续的。所以这些边中合法的选择方案,一定边数相等且形成的联通块相同

原因无他惟手熟尔,假设存在一条不符合上述结论的边e,那么在一开始做kruskal的时候就该把它加进去。为什么?因为若存在这个e,那不是能用更小的代价减少了一个连通分量了吗?也就是说可以得到一个比MST更小的MST(滑稽)。

显然非常非常矛盾。所以上述结论正确。也就同时解释了问题1.2.

代码不贴了。。。