BZOJ 3659 Which Dreamed It

发布于 2017-07-05  244 次阅读


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

题意:求以 1 为起点的欧拉回路的个数乘 1 的度数


没看懂为什么要乘 1 的度数... 惨招题意杀...

首先给个结论:

BEST theorem —— 以某个点为起点的欧拉回路数=该点为根的树形图数*所有点出度-1 的阶乘

那么问题就解决了 T.T..... 这种定理题就是这样的啊...

对了... 另外,矩阵树定理也可以直接套用到有向图上解决树形图个数的问题,邻接矩阵定义不变,度数矩阵为入度

当练板子了...

 


一个非常弱的准退役OIER