hust 1017

题意：求01矩阵的精确覆盖。

分析：本来想学习dancing links来解决数独问题，发现dancing links最初解决的问题是精确覆盖，于是就找到这道题来做了。这种NPC问题只能用DFS暴搜的情况下，很适合的一种优化方式就是用dancing links加速状态的改变，利用双向循环十字链表使元素的删除与恢复操作非常简便快捷。

  1 #include <cstdio>
  2 
  3 int U[102005],D[102005],L[102005],R[102005];
  4 int X[100005],Y[100005],H[1005],S[1005],ans[1005],len,M,N,sz;
  5 
  6 void init(int n,int m)
  7 {
  8     for(int i = 0;i <= m;i++)
  9     {
 10         U[i] = D[i] = i;
 11         L[i + 1] = i;
 12         R[i] = i + 1;
 13         S[i] = 0;
 14     }
 15     R[m] = 0;
 16     L[0] = m;
 17     sz = m + 1;
 18 }
 19 
 20 void remove(int c)
 21 {
 22     //删除一整列
 23     R[L[c]] = R[c];
 24     L[R[c]] = L[c];
 25     //删除行
 26     for(int i = D[c];i != c;i = D[i])
 27     {
 28         for(int j = R[i];j != i;j = R[j])
 29         {
 30             D[U[j]] = D[j];
 31             U[D[j]] = U[j];
 32             S[X[j]]--;
 33         }
 34     }
 35 }
 36 
 37 void resume(int c)
 38 {
 39     //恢复一整列
 40     L[R[c]] = c;
 41     R[L[c]] = c;
 42     //恢复行
 43     for(int i = D[c];i != c;i = D[i])
 44     {
 45         for(int j = R[i];j != i;j = R[j])
 46         {
 47             D[U[j]] = j;
 48             U[D[j]] = j;
 49             S[X[j]]++;
 50         }
 51     }
 52 }
 53 
 54 void ins(int r,int c)
 55 {
 56     S[c]++;
 57     //纵向插入
 58     D[U[c]] = sz;
 59     U[sz] = U[c];
 60     D[sz] = c;
 61     U[c] = sz;
 62     X[sz] = c;
 63     Y[sz] = r;
 64     //横向插入
 65     if(H[r] == -1)
 66     {
 67         H[r] = L[sz] = R[sz] = sz;
 68     }
 69     else
 70     {
 71         R[L[H[r]]] = sz;
 72         L[sz] = L[H[r]];
 73         R[sz] = H[r];
 74         L[H[r]] = sz;
 75     }
 76     sz++;
 77 }
 78 
 79 bool dfs(int k)
 80 {
 81     if(R[0] == 0)
 82     {
 83         len = k;
 84         ans[k] = -1;
 85         return true;
 86     }
 87     else
 88     {
 89         int m = 0xffffff,num;
 90         for(int i = R[0];i != 0;i = R[i])
 91         {
 92             if(S[i] == 0)
 93             {
 94                 return false;
 95             }
 96             if(m > S[i])
 97             {
 98                 m = S[i];
 99                 num = i;
100                 if(m == 1)
101                 {
102                     break;
103                 }
104             }
105         }
106         remove(num);
107         for(int i = D[num];i != num;i = D[i])
108         {
109             ans[k] = Y[i];
110             for(int j = R[i];j != i;j = R[j])
111             {
112                 remove(X[j]);
113             }
114             if(dfs(k + 1))
115             {
116                 return true;
117             }
118             for(int j = R[i];j != i;j = R[j])
119             {
120                 resume(X[j]);
121             }
122         }
123         resume(num);
124     }
125     return false;
126 }
127 
128 int main()
129 {
130     while(~scanf("%d%d",&N,&M))
131     {
132         init(N,M);
133         for(int i = 1;i <= N;i++)
134         {
135             int k;
136             scanf("%d",&k);
137             H[i] = -1;
138             for(int j = 1;j <= k;j++)
139             {
140                 int c;
141                 scanf("%d",&c);
142                 ins(i,c);
143             }
144         }
145         if(dfs(0))
146         {
147             printf("%d",len);
148             for(int i = 0;ans[i] != -1;i++)
149             {
150                 printf(" %d",ans[i]);
151             }
152             printf("
");
153         }
154         else
155         {
156             printf("NO
");
157         }
158     }
159     return 0;
160 }