HDU3957 Dancing Links

好吧，昨天被这题虐惨了，照着模板敲漏了一句话，导致 1005 没有时间写了。这题可以算是一个比较经典的 Dancing Links 的题了，我们将问题抽象这如下一个模型。

大致题意

给你一个 $R \times C$ 的 0-1 矩阵，要求选出最小数量的行使得每一列至少被覆盖一次，并且有限制某一些行中只能至多选择一行。

我们将模型抽象化，有两种方法来解决此类问题。

第一种方法是建立一个有 $2 \times N$ 行，$3 \times N$ 列的矩阵，行代表的是选择哪些人的哪一个形态，前 $2 \times N$ 列代表的是 $N$ 个人的两种形态，后面 $N$ 列表示选择了某个人，这样我们可以这么理解，前 $2 \times N$ 列是我们必须至少覆盖一次的，后 $N$ 列是我么至多覆盖一次的，那么我们就在前 $2 \times N$ 列进行重复覆盖，后面 $N$ 列进行精确覆盖，此外，判断是否得到了一组解，只要判断前 $2 \times N$ 列是否已经被完全覆盖了即可。这个矩阵的规模是 $50 \times 75$ 的。

第二种方法是建立一个 $2 \times N$ 行 $2 \times N$ 列的矩阵，直接跑重复覆盖，此外用一个数组标记某一个人是否被选择过，如果一个人的某一形态被选择过，那么另外一个形态对应的行就不能选择，这个矩阵的规模是 $50 \times 50$ 的。