[知识点] 最小树形图

问题

给定一个 \(n\) 个点 \(m\) 条边的带权简单有向图,求一个最小边权和的是以 \(r\) 为根的内向生成树。

外向树的情况没有本质区别,边反一反就好。

无根的情况可以加一个点转化为有根的情况。

算法

如果给定的有向图是 DAG,一个显然的贪心是,取除了 \(r\) 以外的每个点的最小出边。显然这样会构成一棵内向树,且不可能有权值和更小的内向树。

如果给定的有向图不是 DAG,直接取除了 \(r\) 以外的每个点的最小出边不一定会得到一棵树,此时可能会有多个弱连通块,每个连通块是一条链(包含 \(r\) 的)或者一棵基环内向树。如果你得到了一个内向生成树就求出了答案,下面我们考虑至少有一个环的情况。

可以发现,对于一个(某个基环树连通块中的)环,一定存在一个最小内向生成树,恰好只有一条环上边不在这个最小内向生成树中。原因很简单,我们先假设边权互不相同(你可以加入一个充分小的偏移量,在不影响答案的前提下使边权互不相同),设点 \(u\) 的最大出边连向点 \(f(u)\),考虑一个最小内向生成树,如果存在一个点 \(u \neq r\)\(f(u)\) 不在 \(u\) 的子树中,且 \(f(u)\) 不是 \(u\) 的父亲,我们可以把 \(u\) 的父亲改为 \(f(u)\),得到一个更小的内向生成树,这与这个树是最小内向生成树矛盾。这说明,对于任意一个环上的点 \(u\),使得 \(f(u)\) 不是 \(u\) 的父亲 (环上点肯定不是 \(r\)),\(f(u)\) 要么是 \(u\) 的父亲要么在 \(u\) 的子树中。考虑从 \(u\) 出发,每次从 \(u\) 走向 \(f(u)\),在走回 \(u\) 之前,一定不会经过一个点两次,从而路径上只有第一次走的时候 \(f(u)\) 不是 \(u\) 的父亲,因此环上只有一条边没有在这个最小内向生成树中出现。

因此我们只需要考虑一个环上哪一条边没有出现。考虑把环缩成一个点,得到一个与原图等价的图。

例图
例图

其中 \(e\) 是不在最小树形图中的边,从图中可以很明显地看到,把环缩成一个点,然后把缩完后的的点的出边边权减去原来这条出边对应的 \(e\) 的权值即可得到一个等价的图。

暴力缩点可以用 \(\mathcal O(nm)\) 的时间复杂度求出最小树形图。

复杂度优化

用并查集维护弱连通块,再用并查集维护当前哪些点被缩成了一个点。用可并堆维护当前每个点的出边,缩点时带 tag 合并一下,然后找最小出边,如果在同一弱连通块又可以缩点了,否则的话就和其他弱连通块合并在了一起。

缩一次至少减少一个点,所以这个算法的复杂度为 \(\mathcal O((n+m) \log n)\)

实现

咕咕咕。

由于实现咕了所以也不能保证上面说的是对的。