0%

xhr 的奇思妙想

恩,大概是这么个问题:

给定一个图,每次对于一个联通块,随机删除一棵生成树,期望多少次删完所有的边?

于是想了一下没有结果,打个程序试试,发现随机图上差不多就是 m/n 了。

关于这个数,xhr 说一定不超过原图两点间最大流的最大值,因为每次起码会破坏一条增广路。

然后呢?不知道了。

于是乎 xhr 又 YY 了一个题(据 Vani 说是 Asia Regional 2012 Chengdu 的原题):

给定一个图 G = (V, E) ,保证 \|E\| <= 5\|V\| ,每次修改一个点,查询一个点所有邻居的权和。

\|V\| <= 20w, Q <= 100w

有了这个 图树剖分 还是蛮简单的吧。

我肿么感觉我就是打了一圈酱油呢?

update

从网上找到篇论文: Disjoint Spanning Trees 1 Forest Partitioning link

里面有这么句话:

The minimum number of forests needed to cover the edges of a graph G is
    max{ceil(\|A\| / rank(A)) : A in E}

其中 rank(A) 的定义是 A 的顶点数减去连通块个数。

也就是说,如果没有重边,那么剖分数至多是 O(sqrt(m)) 的。随机图就更不用说了。好像用来骗分很爽的