hdu 5729 Rigid Frameworks

题意：题目非常长，前面讲了一大堆刚性的和灵活的，但是问的是网格图。很显然网格图不是刚性的（如下图），但是我们可以通过添加对角线使得它变为刚性的，问有多少种添加的方法使变为刚性的。 题解：可以(很难)发现，在摆动过程中，原来处于同一行的竖边一定平行；同理，原来处于同一列的横边一定平行。我们要做的即为所有横边垂直于所有竖边，那么一行和一列可以分别看做整体。更进一步地，如果两行竖边都垂直于同一列横边，这两行就属于同一个集合。 这里使用一个经典模型，将网格图的行和列作为二分图的左右两个点集，(x,y)连边就表示x行的竖边垂直于y列的横边，那么问题可以转化为最终n+m个点都连通的方案数。但是要注意，连边和添加对角线并不完全等价！添加对角线包含了主对角线和次对角线，而普通的连边没有这种含义。

我们设计一种动态规划（或者说递推），那它必然是总方案数减去不可行的方案数： dp[n][m]=3nm−∑i=1,j=0i<n||j<mCi−1n−1Cjm⋅dp[i][j]⋅3(n−i)(m−j) $$dp[n][m]=3^{nm}-/sum_{i=1,j=0}^{i<n||j<m} C_{n-1}^{i-1}C_{m}^{j}/cdot dp[i][j]/cdot 3^{(n-i)(m-j)}$$ 3nm$3^{nm}$表示对于每一个格子我们总是有无对角线，主对角线，次对角线三种选择。后面的减数项中，为了保证不重复，我们总是枚举左边明确的某一点（例如1$1$号点）所在的连通块的左右大小。具体地，我们从2−n$2-n$号点中选出i−1$i-1$个，从m$m$个点中选出j$j$个，它们内部会有dp[i][j]$dp[i][j]$种方案，至于剩下的n−i$n-i$个点和m−j$m-j$个点的关系，任意选择即可。

理解了之后写代码非常简单，可以用预处理做到O(n4)$O(n^4)$