HDU 5724 Rigid Frameworks

Posted on By 二价氢

http://acm.hdu.edu.cn/showproblem.php?pid=5729

题目大意

给定一个由个小方格组成的木框,显然它是不稳定的,现在要向其中的某些小方格的对角线加上木条使其成为稳定的木框,求方案总数。

思路及做法

通过手玩,可以发现以下条件:

  1. 每行至少有一个对角线上有木条
  2. 每列至少有一个对角线上有木条
  3. 行(列)之间需要有相交的部分(此句说得不是特别清楚,自己感受大意,例子就是的格子至少得有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