本文主要是介绍bzoj2467[中山市选2010]生成树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2467
题目大意：
有一种图形叫做五角形圈。一个五角形圈的中心有1个由n个顶点和n条边组成的圈。在中心的这个n边圈的每一条边同时也是某一个五角形的一条边，一共有n个不同的五角形。这些五角形只在五角形圈的中心的圈上有公共的顶点。如图0所示是一个4-五角形圈。
现在给定一个n五角形圈，你的任务就是求出n五角形圈的不同生成树的数目。还记得什么是图的生成树吗？一个图的生成树是保留原图的所有顶点以及顶点的数目减去一这么多条边,从而生成的一棵树。
注意：在给定的n五角形圈中所有顶点均视为不同的顶点。
题解：
先把每个五边形缩成一条边来看，就成了一个n边形，得到生成树的话要从中选一条边割掉。
而对于其余的没有被割的五边形来说，都要选择一条边割掉，因为五边形成环。
但是会发现一开始被割的那个五边形可以与其余的成环(少割了一条边)，无论其余的怎么割。
即有一个五边形割了两条边(其中一边在中间的n边形上)，其余五边形割了一条边。
那么生成树的数目就是n*4*5^(n-1)。
n是枚举哪个五边形割两条边，4是枚举那个五边形被割了哪条(有一边必在中间的n边形上嘛)，然后对于其他的n-1个五边形就枚举割哪条边就是5啊，n-1个就是5^（n-1）。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;const int mod=2007;
int qk(int x,int t)
{int ret=1;while (t){if (t&1) ret=(ret*x)%mod;x=(x*x)%mod;t>>=1;}return ret;
}
int main()
{//freopen("tree.in","r",stdin);//freopen("tree.out","w",stdout);int n,ans,T;scanf("%d",&T);while (T--){scanf("%d",&n);ans=(((4*qk(5,n-1))%mod)*n)%mod;printf("%d\n",ans);}return 0;
}
这篇关于bzoj2467[中山市选2010]生成树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
