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


题目链接: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)}$$

具体可以画图感受一下

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 2467 [中山市选 2010] 生成树


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: ,