题目链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=65998#problem/A

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

DLX学习资料:http://www.cnblogs.com/grenet/p/3145800.html

http://blog.csdn.net/mu399/article/details/7627862

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 10007
#define inf 0x3f3f3f3f
#define N 100010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int maxnode=;
const int MaxN=;
const int MaxM=;
struct DLX
{
int n,m,size;
int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];
int H[MaxN],S[MaxM];
int ansd,ans[MaxN];
void init(int _n,int _m)
{
n=_n;m=_m;
for(int i=;i<=m;i++)
{
S[i]=;
U[i]=D[i]=i;
L[i]=i-;
R[i]=i+;
}
R[m]=;L[]=m;
size=m;
for(int i=;i<=n;i++)H[i]=-;
}
void Link(int r,int c)
{
++S[Col[++size]=c];
Row[size]=r;
D[size]=D[c];
U[D[c]]=size;
U[size]=c;
D[c]=size;
if(H[r]<)H[r]=L[size]=R[size]=size;
else
{
R[size]=R[H[r]];
L[R[H[r]]]=size;
L[size]=H[r];
R[H[r]]=size;
}
}
void Remove(int c)
{
L[R[c]]=L[c];R[L[c]]=R[c];
for(int i=D[c];i!=c;i=D[i])
for(int j=R[i];j!=i;j=R[j])
{
U[D[j]]=U[j];
D[U[j]]=D[j];
--S[Col[j]];
}
}
void Resume(int c)
{
L[R[c]]=R[L[c]]=c;
for(int i=U[c];i!=c;i=U[i])
for(int j=L[i];j!=i;j=L[j])
++S[Col[U[D[j]]=D[U[j]]=j]];
}
bool Dance(int d)
{
if(R[]==)
{
ansd=d;
return true;
}
int c=R[];
for(int i=R[];i!=;i=R[i])
if(S[i]<S[c])c=i;
Remove(c);
for(int i=D[c];i!=c;i=D[i])
{
ans[d]=Row[i];
for(int j=R[i];j!=i;j=R[j])Remove(Col[j]);
if(Dance(d+))return true;
for(int j=L[i];j!=i;j=L[j])Resume(Col[j]);
}
Resume(c);
return false;
}
};
DLX g;
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)>)
{
g.init(n,m);
for(int i=;i<=n;i++)
{
int num,j;
scanf("%d",&num);
while(num--)
{
scanf("%d",&j);
g.Link(i,j);
}
}
if(!g.Dance())puts("NO");
else
{
printf("%d",g.ansd);
for(int i=;i<g.ansd;i++)printf(" %d",g.ans[i]);
puts(""); }
}
}

最新文章

  1. 如何开发FineReport的自定义控件?
  2. Vue.js&mdash;&mdash;60分钟browserify项目模板快速入门
  3. soap发送报文请求和dom4j解析XML并且获得指定名称的节点信息
  4. Sharepoint2013切换用户菜单
  5. information_schema系列之字符集校验(CHARACTER_SETS,COLLATIONS,COLLATION_CHARACTER_SET_APPLICABILITY)
  6. HANA Studio打开系统显示Secure storage is locked
  7. Spring MVC 详解(二)
  8. 【原创】Freak3D printer 的Repetier-Host 的设置
  9. 【JAVAWEB学习笔记】05_jQuery基础
  10. 神奇的background
  11. SSM框架整合,以CRM为例子
  12. 女儿开始bababababa的发声了
  13. Elasticsearch.安装插件(head)
  14. windows下redis 配置文件参数说明
  15. nginx rewrite重写
  16. Idea设置行注释不显示在行首
  17. LOJ 530 最小倍数(数论)
  18. Linux文件时间详解ctime、mtime、atime【转】
  19. 操作系统概念学习笔记三 cpu调度算法
  20. js需要清楚的内存模型

热门文章

  1. Not able to reset SmartRF04DD
  2. [置顶] js中如何复制一个对象,如何获取所有属性和属性对应的值
  3. iot 表索引dump《2》
  4. android:改动PagerTabStrip中的背景颜色,标题字体的样式、颜色和图标以及指示条的颜色
  5. 【UVA】12299-RMQ with Shifts(线段树)
  6. win32 字体变换与窗口同大同小
  7. java开发异常类型汇总
  8. 阅读代码分析工具Understand 2.0试用
  9. 【IOS实例小计】打开google地图-web
  10. Cocos2d-x 创建(create)动画对象CCAnimation报错分析