http://acm.hdu.edu.cn/showproblem.php?pid=5729
题目大意
给定一个由个小方格组成的木框,显然它是不稳定的,现在要向其中的某些小方格的对角线加上木条使其成为稳定的木框,求方案总数。
思路及做法
通过手玩,可以发现以下条件:
- 每行至少有一个对角线上有木条
- 每列至少有一个对角线上有木条
- 行(列)之间需要有相交的部分(此句说得不是特别清楚,自己感受大意,例子就是的格子至少得有4个格子有对角线)
具体的含义为,位于的对角线把第i行和第j列的转动连在了一起,而最终的答案中不能有两个不相关的转动变量(第三条)。
通过这一点,可以得知题目的模型是个二分图,其中一侧为行,另一侧为列,i行j列的对角线相当于左边第i个节点与右边第j个节点之间的边,意味着它们有一样的转动变量,而最终题目要求是整个图只有一个转动变量,意味着这个二分图是个联通图。
由图论的一些知识,我们可以知道,有n个节点、m条边的连通图个数为,其中表示不连通的图的数量,不连通的图,一定可以分为两个子图,其中一个连通,其中第n个结点在连通的子图当中,即不连通的图的个数为
将其减去即得到了连通图的数量。
对于这一题,求二分图连通图的数量,也可以使用类似的方法,首先,我们知道,所以不妨设,则有,表示有n+m个结点,k条边的二分连通图的个数,显然,边界条件为,同时,类似的可以得到
最后,答案为
算法复杂度为
AC-Code (C++)
Time 0MS, Memory 1784K
https://github.com/erjiaqing/my_solutions/blob/master/hdu/5729.cpp