传送门:HUST1017
【题意】给定一个由0-1组成的矩阵,是否能找到一个行的集合,使得集合中每一列都恰好包含一个1。
【分析】学习了DLX,DLX模版题,详情跳跃的舞者,舞蹈链(Dancing Links)算法——求解精确覆盖问题关于一点,恢复的时候需要倒过来可以加快速度,正着恢复会有很多已经恢复过的再重复恢复,导致没列计数不准确,速度会慢很多。所以一般倒着恢复再加每列计数。
【AC CODE】184ms
#include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <set> //#include <unordered_set> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f, MAXN = 1000+10, M = MAXN*100; int n,m; /*行标,列标都是1~n,和1~m*/ struct DLX{ private: int lt[M],rt[M],up[M],down[M],row[M],col[M],tol;//舞蹈链(交叉十字循环双向链)内存池 int cnt[MAXN];//每一列还有多少个结点 void remove(int c)//删除c列含有1的全部行 { lt[rt[c]] = lt[c];rt[lt[c]] = rt[c]; for(int i = down[c]; i != c; i = down[i]) { for(int j = rt[i]; j != i; j = rt[j]) { down[up[j]] = down[j];up[down[j]] = up[j]; --cnt[col[j]]; } } } void reset(int c)//恢复被删除的c列含有1的全部行 { for(int i = up[c]; i != c; i = up[i]) { for(int j = lt[i]; j != i; j = lt[j]) { down[up[j]] = up[down[j]] = j; ++cnt[col[j]]; } } lt[rt[c]] = rt[lt[c]] = c; } public: void init(int m)//总共有m列 { repe(i,0,m)//第0行的虚拟结点 { lt[i] = i-1,rt[i] = i+1; up[i] = down[i] = i; } lt[0] = m;rt[m] = 0;//循环 tol = m+1; clc(cnt,0); } void add_row(int r,int len, int *a)//向舞蹈链r行添加一整行结点 { int ft = tol; rep(i,0,len) { int c = a[i]; row[tol] = r,col[tol] = c; lt[tol] = tol-1,rt[tol] = tol+1,up[tol] = up[c],down[tol] = c; down[up[c]] = tol,up[c] = tol; cnt[c]++,tol++; } lt[ft] = tol-1, rt[tol-1] = ft; } int ansd,ans[MAXN]; bool dance(int d) { if(0 == rt[0])//所有列都被覆盖,找到答案 { ansd = d; return true; } int c = rt[0];//第一个没被覆盖的列c for(int i = rt[0]; i; i= rt[i]) if(cnt[i] < cnt[c]) c = i;//优化,选择列上行数最小的那列,可以减少重复覆盖的概率,加快搜索 remove(c); for(int i = down[c];i != c; i = down[i])//删除c列为1的所有行 { ans[d] = row[i]; for(int j = rt[i]; j != i; j = rt[j]) remove(col[j]);//把删除行所占的列也删除 if(dance(d+1)) return true; for(int j = lt[i]; j != i; j = lt[j]) reset(col[j]); } reset(c); return false; } }dlx; int main() { #ifdef SHY freopen("d:\\1.txt", "r", stdin); #endif while(~scanf("%d %d", &n, &m)) { int a[110]; dlx.init(m); repe(i,1,n) { int len; scanf("%d", &len); rep(j,0,len) scanf("%d",&a[j]); sort(a,a+len); dlx.add_row(i,len,a); } if(dlx.dance(0)) { printf("%d",dlx.ansd); rep(i,0,dlx.ansd) printf(" %d", dlx.ans[i]); putchar('\n'); } else puts("NO"); } return 0; }