SGU 481..Hero of our time

正经的写一篇题解吧。这个题目求的是有标号的n个点n条边的联通图的数量。n  <=5000

往往题目异常简洁的题目会比较难>_<。。。

分析1:

这个图必然是一个环加上一个外向树的形式。

思路1 or 2:

那么接下来就有两个思路了,要么固定环,想办法算出答案,要么选一个点为根,在这个有根树中考虑这个环。

思路1:

尝试固定环,设环大小为k,那么在这个图中去掉这些环上的边,得出的就是n个点,k棵树的森林。

令F(n,k)表示n个点,k棵树的森林的个数,那么环大小为k的情况答案是:

F(n,k)*k!/2。。这不难理解。。因为森林出来之后森林的那些根的园排列有k!/2种。

考虑如何求F(n,k)。

思路 1.1 or 1.2:

要么将F(n,k)看成一个二维递推式,推导出结果。 要么尝试使用组合数学的方法直接计算出F(n,k)。

思路 1.1:

考虑一棵树,为了在递推中不影响树的大致的整体结构(最大相似性决定递推的成功>_<)。我们可以

尝试取走一个叶子来将树的大小-1

那么令G(n,t)表示n个节点,t个叶子的树的个数。

考虑两种规划的方式,正向和逆向,逆向规划(即在算G(n,t)时用以前的结果)的关键在于取走一个叶子之后,不能知道叶子的父亲是否

会变成叶子,而叶子数是很重要的,所以不可行。正向规划相反则是可行的(即用G(n,t)更新G(n+1,..)的)结果。

考虑当前是G(n,t),如果加入一个叶子,那么可以连到叶子节点上,也可以连到非叶子节点上。

前者叶子数不变,后者叶子数+1。就可以较方便的计算了。

但是每个G(n,t)在计算的时候,它的每个叶子都会把它的结果计算一遍,所以最后要除以t。

但是这是n^2的,而且还涉及高精度的问题。所以不是一个好算法。

思路 1.2:

在推导标号树个数的时候有一种方法叫双重计数,同样可以解决计算F(n,k)的问题。

并能给出一个直接的公式

没时间就不展开了。。。可以自己去看wiki

复杂度是O(N)。

http://en.wikipedia.org/wiki/Double_counting

 

思路2:

令1为根,那么我们可以找到环中最接近1的点(注意,满足唯一性!计数问题必不可少的)

令其为x,考虑x在环上的两个相邻点l和r。

令l<r。。去掉边x->r。就变成了一棵树,还是以1为根可以发现l是r的祖先。

可以发现在“1为根,x在环上的相邻点是l和r且l<r的结果” = “1为根,l<r且l是r的祖先的树的个数”

那么后者的结果乘以每句l和r造成的C(n-1,2)就是答案。

如何求后者呢?

有一种prufer Code的推广形式能轻易的给出答案。。由于非常繁琐就不说了。。

http://www.cs.elte.hu/egres/tr/egres-05-16.pdf

 

。。。我发现写这么多还不如直接贴5、6个网址让大家自己去看。。。。

我2。。。。

5 thoughts on “SGU 481..Hero of our time

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>