题目描述
Dancing Links X 求解精确覆盖问题
给定一个 N×M 的数字矩阵 A,矩阵中的元素 Ai,j∈{0,1}。
请问,你能否在矩阵中找到一个行的集合,使得这些行中,每一列都有且仅有一个数字 1。
输入格式
第一行包含两个整数 N 和 M。
接下来 N 行,每行包含 M 个整数(0 或 1),表示完整的数字矩阵。
输出格式
如果能找到满足条件的行的集合,则在一行中依次输出这些行的编号(行编号 1∼N)。
如果方案不唯一,则以任意顺序输出任意方案即可。
否则,输出 No Solution!。
样例输入
3 3
0 1 0
0 0 1
1 0 0
样例输出
1 2 3
代码
//具体内容都在代码里啦
#include<bits/stdc++.h>
using namespace std;
const int N=505;//n,m的大小
const int M=N*N+N;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int n,m,cnt;//矩阵的长宽及点的数量
int u[M],d[M],l[M],r[M];//每个点上下左右的指针
int row[M],col[M];//每个点所在的行列
int h[M];//每行的头节点
int s[M];//每列的节点数
int ans[M];//选了哪些集合
void build(int m)//建立一个空矩阵
{
for(int i=0;i<=m;i++)
{
l[i]=i-1;
r[i]=i+1;
u[i]=d[i]=i;
}
l[0]=m;//0左边是m
r[m]=0;//m右边是0
//构建循环链表
memset(h,-1,sizeof(h));
memset(s,0,sizeof(s));
cnt=m+1;//一开始空矩阵有m+1个元素
}//初始化 生成每列的头
inline void link(int R,int C)//在第R行C列插入一个元素
{
s[C]++;//第C列元素个数增加
row[cnt]=R;//当前插入的点编号为cnt
col[cnt]=C;//记录当前点的行列信息
u[cnt]=C;
d[cnt]=d[C];
u[d[C]]=cnt;//对于列:这个点是直接插到该列的虚拟节点的后面
d[C]=cnt;//构建双向十字链表-列
if(h[R]==-1)//如果该行中没有其它点
{
h[R]=cnt;//以该点作为第R行的头节点
l[cnt]=r[cnt]=cnt;//作为当前该行唯一的节点兼头节点 它的左右指针都指向它自己
}
else//构建双向十字链表-行
{
r[cnt]=h[R];//对于行:这个点是插入到该行的末尾
l[cnt]=l[h[R]];
r[l[h[R]]]=cnt;
l[h[R]]=cnt;//完美闭环...(DARK:???)
}
cnt++;//节点编号加1
return;
}
inline void remove(int C)//删除第C列及该列上有元素的每一行
{
r[l[C]]=r[C];//该列左边元素指向该列的右指针直接指向该列的右边 相当于直接把该列忽视掉了
l[r[C]]=l[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];//注意我们处理的点是该列有1的行内的点
d[u[j]]=d[j];//将我们要处理的点在这个点的纵向删除掉
s[col[j]]--;//这个点所在的列元素数量减1
}
}//不难发现 删除的本质分为两步:单独处理掉本列; 在横向以点为单位逐个删除掉
inline void resume(int C)//恢复本列及相关元素
{
for(int i=u[C];i!=C;i=u[i])//遍历相关行
for(int j=l[i];j!=i;j=l[j])//遍历行上的点
{
u[d[j]]=j;//将该点与上下节点的关系恢复回来
d[u[j]]=j;
s[col[j]]++;//将该点所在的列上的元素个数加回来
}
r[l[C]]=C;//删除与恢复的对称之美
l[r[C]]=C;
}
bool dance(int depth)//depth表示准备选择第几行
//注: 这里的第几行不是指在矩阵中的第几行; 在选第depth行时 还并没有确定选了谁
{
if(r[0]==0)//矩阵空了 搜索成功
{
for(int i=1;i<depth;i++)//是< 而不是≤
cout<<ans[i]<<" ";//输出选中了哪几行
return 1;//返回true表示这种选择方案能满足条件
}
int c=r[0];
for(int i=r[0];i!=0;i=r[i])//从左到右遍历列
if(s[i]<s[c])//找到元素最少的那一列
c=i;
remove(c);//删除元素最少的那一列 减少搜索次数
for(int i=d[c];i!=c;i=d[i])//从上往下遍历c列有元素的行
{
ans[depth]=row[i];//假定选择该行
for(int j=r[i];j!=i;j=r[j])//删除这一行中有元素的列
remove(col[j]);
if(dance(depth+1))//递归搜索该方案是否满足条件
return 1;
for(int j=l[i];j!=i;j=l[j])//复原
resume(col[j]);
}
resume(c);//不要忘记同时要恢复c本身这一列
return 0;
}
int main()
{
n=read();
m=read();
build(m);//建立空图(但加有列上的虚拟节点)
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int x=read();
if(x==1)//将需要的元素添加到链表中
link(i,j);
}
if(!dance(1))
puts("No Solution!");
return 0;
}