$$\color{Purple}{kuangbin题解目录}$$
$$\color{SpringGreen}{Dancing\ Links参考学习链接1}$$
$$\color{Gold}{Dancing\ Links参考学习链接2}$$
题目描述
给定一个 $N$ 行 $M$ 列的矩阵,矩阵中每个元素要么是 $1$,要么是 $0$。
你需要在矩阵中挑选出若干行,使得对于矩阵的每一列 $j$,在你挑选的这些行中,有且仅有一行的第 $j$ 个元素为 $1$。
输入格式
第一行两个数 $N,M$。
接下来 $N$ 行,每行 $M$ 个数字 $0$ 或 $1$,表示这个矩阵。
输出格式
一行输出若干个数表示答案,两个数之间用空格隔开,输出任一可行方案均可,顺序随意。
若无解,输出 No Solution!
。
样例 #1
样例输入 #1
3 3
0 0 1
1 0 0
0 1 0
样例输出 #1
2 1 3
样例 #2
样例输入 #2
3 3
1 0 1
1 1 0
0 1 1
样例输出 #2
No Solution!
提示
对于 $100\%$ 的数据,$N,M\leq 500$,保证矩阵中 $1$ 的数量不超过 $5000$ 个。
代码
- 注意插入结点的方式和恢复和删除交换顺序问题
// Problem: P4929 【模板】舞蹈链(DLX)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4929
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Date: 2023-01-13 15:12:50
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 510
#define MAXM 6010
//题目已知1元素5000个,加上行列共1000个
using namespace std;
typedef long long ll;
int n,m;
struct Dancing_Links_Node{
int Up;
int Down;
int Left;
int Right;
int row;//行数
int col;//列数
};
int cnt=0;//记录结点个数
Dancing_Links_Node node[MAXM];
int f_row[MAXN];//记录每行的第一个元素
int c_cnt[MAXN];//每列元素个数
int res[MAXN];//保存最终结果
void Init_Node(int num)//初始化head和列元素,将其上下左右指针指好,行数和列数可不用初始化
{
for(int i=0;i<=num;i++)
{
node[i].Left=i-1;//左-1
node[i].Right=i+1;//右+1
node[i].Up=i;//上下指向自己
node[i].Down=i;
c_cnt[i]=0;//列个数清空
}
node[0].Left=num;//让head的左边指向最后一个的列元素
node[num].Right=0;//让最后一个的列元素的右边指向head
cnt=num;//更新结点个数
memset(f_row,-1,sizeof(f_row));
}
void Insert_Node(int x,int y){//插入新节点(链式前向星的构图方式)
//更新具体值
node[++cnt].row=x;//更新行数
node[cnt].col=y;//更新列数
//先处理该结点的所在列链上的情况
node[cnt].Down=node[y].Down;//更新当前元素的指向下面
node[node[y].Down].Up=cnt;//之前的最后一个元素指向最后
node[cnt].Up=y;
node[y].Down=cnt;
//然后处理该结点的所在行链上的情况
if(f_row[x]<0)//表示该结点是其所在行的第一个元素
{
node[cnt].Left=cnt;//自己指向自己
node[cnt].Right=cnt;//自己指向自己
f_row[x]=cnt;//更新当前行的第一个元素
}
else//表示该结点不是其所在行的第一个元素
{
node[cnt].Right=node[f_row[x]].Right;
node[node[f_row[x]].Right].Left=cnt;
node[cnt].Left=f_row[x];
node[f_row[x]].Right=cnt;
}
c_cnt[y]++;//当前列元素+1
}
void Remove_Link(int y)//删除列元素所在的列链 及 其中元素所对应行
{
for(int i=node[y].Down;i!=y;i=node[i].Down)//枚举列链中的元素
for(int j=node[i].Right;j!=i;j=node[j].Right)//枚举列链中元素所对应行链中元素并删除
{
node[node[j].Down].Up=node[j].Up;
node[node[j].Up].Down=node[j].Down;
//当前元素删除后,该元素的下面元素指向上面的是当前元素的上面元素
//当前元素删除后,该元素的上面元素指向下面的是当前元素的下面元素
c_cnt[node[j].col]--;//当前列的元素-1
}
//删除列链(仅需删除列元素即可删除整个列链)
node[node[y].Left].Right=node[y].Right;
node[node[y].Right].Left=node[y].Left;
//当前列元素的左面元素指向右边面的是当前元素的右面元素
//当前列元素的右面元素指向左边面的是当前元素的左面元素
}
void Resume_Link(int y)//恢复列元素所在列链 及 其中元素所对应行
{
//恢复列链(仅需恢复列元素即可恢复整个列链)
node[node[y].Left].Right=y;
node[node[y].Right].Left=y;
for(int i=node[y].Up;i!=y;i=node[i].Up)//枚举列链中的元素
for(int j=node[i].Left;j!=i;j=node[j].Left)//枚举列链中元素所对应行链中元素并恢复
{
node[node[j].Down].Up=j;
node[node[j].Up].Down=j;
//当前元素的上面元素指向下面的是当前元素
//当前元素的下面元素指向上面的是当前元素
c_cnt[node[j].col]++;//当前列的元素+1
}
}
int dance(int depth)//depth表示答案的个数(所搜的层数)
{
if(node[0].Right==0)//如果head.right=head,说明有解,输出答案
{
for(int i=0;i<=depth-1;i++)
printf("%d ",res[i]);
printf("\n");
return 1;
}
int y=node[0].Right;//取列元素y=head.right
for(int i=node[0].Right;i!=0;i=node[i].Right)//剪枝(减少搜索树的分叉)
if(c_cnt[i]<c_cnt[y])
y=i;
Remove_Link(y);//删除列链
for(int i=node[y].Down;i!=y;i=node[i].Down)
{
res[depth]=node[i].row;
for(int j=node[i].Right;j!=i;j=node[j].Right)//删除选择行链元素所在列链
Remove_Link(node[j].col);
if(dance(depth+1)==1)
return 1;
for(int j=node[i].Left;j!=i;j=node[j].Left)//恢复选择行链元素所在列链
Resume_Link(node[j].col);
}
Resume_Link(y);//恢复列链
return 0;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> n >> m;
Init_Node(m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int num;
cin >> num;
if(num==1)
Insert_Node(i,j);
}
if(dance(0)==0)
cout << "No Solution!" << endl;
return 0;
}