BZOJ 2467 [中山市选 2010] 生成树

发布于 2017-06-14  133 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2467

题意:对于一个 n 边形,每条边向外扩展出一个五边形,求这个图的生成树个数...


想练习下矩阵树定理找到这题,看了看发现好像可以推式子解决... 于是就解决了...

首先原图有 5n 个点,5n 条边,n+1 个环,显然需要删除 n+1 条边破坏每个环,所以 每个五边形必须破坏一条不属于中间 n 边形的边,中间的 n 边形破坏一条边

对于中间的 n 边形,有 n 种选择,此外对于 n 边形破坏边的对应五边形,只有 4 种选择剩余,而其它五边形有 5 种选择

$$ans=4n*5^{(n-1)}$$

具体可以画图感受一下

 


一个非常弱的准退役OIER