BZOJ2467[中山市选2010]生成树（组合数学）

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id&＃61;2467

【题目大意】

　　有一种图形叫做五角形圈。一个五角形圈的中心有1个由n个顶点和n条边组成的圈。
　　在中心的这个n边圈的每一条边同时也是某一个五角形的一条边&＃xff0c;一共有n个不同的五角形。
　　这些五角形只在五角形圈的中心的圈上有公共的顶点。
　　求该图的最小生成树。

【题解】

　　Matrix-Tree定理超时&＃xff0c;回来找规律&＃xff0c;我们发现对于每个五边形来说&＃xff0c;
　　它至少要删去一条边&＃xff0c;所以每增加一个答案就乘5&＃xff0c;剩余部分是一个环套外向树&＃xff0c;
　　某个五边形要多删去一条边&＃xff0c;而对于这个五边形来说&＃xff0c;删去的两个边有一条必须是多边形上的&＃xff0c;
　　因此基础答案是4。

【代码】