学步园

这题因为建图卡了好久，Dancing Links的入门题，不想多说什么。想了解的请参看Knuth的论文。

这里学会了一个很方便的双向链表插入算法，如果要将x插入到双向链表中，只要先更新x的指针域，然后调用dlx的第二步就可以了。

在init函数有所实现。

我的代码：

#include <cstdio><br /> #include <cstring><br /> #include <cstdlib><br /> #include <algorithm><br /> #define DEBUG</p> <p>using namespace std;</p> <p>const int nColumn = 1100;<br /> const int nRow = 1100;<br /> const int nNode = nRow*nColumn;<br /> const int head = 0;<br /> const int oo = 0x3f3f3f3f;</p> <p>int right[nNode], left[nNode], up[nNode], down[nNode];<br /> int cnt[nColumn];<br /> int result[nNode], nResult;<br /> int row[nRow][nColumn], column[nColumn][nRow];<br /> int cntRow[nRow], cntColumn[nColumn];<br /> int nR, nC;</p> <p>int getColumn(int id) {<br /> if (id % nC)<br /> return id % nC;<br /> else<br /> return nC;<br /> }</p> <p>int getId(int r, int c) {<br /> return r * nC + c;<br /> }</p> <p>int getRow(int id) {<br /> return (id - 1) / nC;<br /> }</p> <p>void remove(const int& x) {<br /> left[right[x]] = left[x];<br /> right[left[x]] = right[x];<br /> for (int r = down[x]; r != x; r = down[r]) {<br /> for (int c = right[r]; c != r; c = right[c]) {<br /> up[down[c]] = up[c];<br /> down[up[c]] = down[c];<br /> cnt[getColumn(c)]--;<br /> }<br /> }<br /> }</p> <p>void resume(const int& x) {<br /> for (int r = up[x]; r != x; r = up[r]) {<br /> for (int c = left[r]; c != r; c = left[c]) {<br /> cnt[getColumn(c)]++;<br /> up[down[c]] = c;<br /> down[up[c]] = c;<br /> }<br /> }<br /> left[right[x]] = x;<br /> right[left[x]] = x;<br /> }</p> <p>bool dfs(const int& k) {<br /> if (right[head] == head) {<br /> nResult = k;<br /> return true;<br /> }<br /> int S = oo, x = 0;<br /> for (int t = right[head]; t != head; t = right[t]) {<br /> if (cnt[t] < S) {<br /> S = cnt[t];<br /> x = t;<br /> }<br /> }<br /> remove(x);<br /> for (int r = down[x]; r != x; r = down[r]) {<br /> result[k] = getRow(r);<br /> for (int c = right[r]; c != r; c = right[c]) {<br /> remove(getColumn(c));<br /> }<br /> if (dfs(k + 1))<br /> return true;<br /> for (int c = left[r]; c != r; c = left[c]) {<br /> resume(getColumn(c));<br /> }<br /> }<br /> resume(x);<br /> return false;<br /> }</p> <p>bool init(int r, int c) {<br /> int id, pre;</p> <p> //deal with list heads<br /> left[head] = c;<br /> right[head] = 1;<br /> for (int i = 1; i <= c; i++) {<br /> left[i] = i - 1;<br /> right[i] = (i + 1) % (c + 1);<br /> up[i] = down[i] = i;<br /> cnt[i] = cntColumn[i];<br /> if (cnt[i] == 0)<br /> return false;<br /> }</p> <p> //deal with columns<br /> for (int i = 1; i <= c; i++) {<br /> for (int j = 0; j < cnt[i]; j++) {<br /> id = getId(column[i][j], i);<br /> up[id] = i;<br /> down[id] = down[i];<br /> up[down[id]] = id;<br /> down[up[id]] = id;<br /> left[id] = right[id] = id;<br /> }<br /> }</p> <p> //deal with rows<br /> for (int i = 1; i <= r; i++) {<br /> for (int j = 1; j < cntRow[i]; j++) {<br /> id = getId(i, row[i][j]);<br /> pre = getId(i, row[i][j - 1]);<br /> left[id] = pre;<br /> right[id] = right[pre];<br /> left[right[id]] = id;<br /> right[left[id]] = id;<br /> }<br /> }<br /> return true;<br /> }</p> <p>int main() {<br /> int x;</p> <p>#ifdef DEBUG1<br /> freopen("in.txt", "r", stdin);<br /> #endif</p> <p> while (~scanf("%d%d", &nR, &nC)) {<br /> for (int i = 1; i <= nC; i++) {<br /> cntColumn[i] = 0;<br /> }<br /> for (int i = 1; i <= nR; i++) {<br /> scanf("%d", &cntRow[i]);<br /> for (int j = 0; j < cntRow[i]; j++) {<br /> scanf("%d", &x);<br /> row[i][j] = x;<br /> column[x][cntColumn[x]++] = i;<br /> }<br /> }<br /> if (!init(nR, nC)) {<br /> puts("NO");<br /> continue;<br /> }<br /> if (!dfs(0)) {<br /> puts("NO");<br /> continue;<br /> }</p> <p> printf("%d", nResult);<br /> for (int i = 0; i < nResult; i++) {<br /> printf(" %d", result[i]);<br /> }<br /> puts("");<br /> }</p> <p> return 0;<br /> }<br />