算法思路
其实这就是一个比较高端的暴力，以模板题为例，其实就是先选其中含 \(1\) 较为少的一列，然后枚举选各个含 \(1\) 的行时其他的列能排除多少行，如果每行都有了就输出，否则要么继续，要么回溯。
如何建链表图
其实这就很简单了，只需要连接数据的上下左右边，再记录一下这一列有几个 \(1\) 与位置即可。
图片展示
初始化函数
void build()
{
int n,m;
cin>>n>>m;
for(int i=0;i<=n;i++)//初始化每一列
{
a[i].l=i-1;
a[i].r=i+1;
a[i].u=i;
a[i].d=i;
s[i]=0;
}
a[0].l=m;//特殊节点特殊写，形成环
a[m].r=0;
int cut=m+1;
for(int i=1;i<=n;i++)//插入行
{
int end,begin;//begin行头，end行尾
end=begin=cut;
for(int j=1;j<=m;j++)
{
int x;
cin>>x;
if(x!=0)
{
s[j]++;//第j列元素个数加一
//记录位置
a[cut].hang=i;
a[cut].lie=j;
//列的链接
a[a[j].u].d=cut;//找到上面一个建边
a[cut].u=a[j].u;
a[cut].d=j;//与头建边
a[j].d=cut;
//行的建边
a[cut].l=end;
a[cut].r=begin;
a[end].r=cut;
a[begin].l=cut;
end=cut;
cut++;
}
}
}
}
如何删除与重新连接边
我们删除一条边其实只需要通过链表每一列的头的删除操作直接连不到这条边，然后把选中的这条边的每一个含一的上下删除即可。
删除边图片展示
删除函数
void del(int num)//删去选中的行的所在列和这一列中有1的行
{
a[a[num].r].l=a[num].l;
a[a[num].l].r=a[num].r;//删除选中的列
for(int i=a[num].d;i!=num;i=a[i].d)
{
for(int j=a[i].r;j!=i;j=a[j].r)
{
a[a[j].d].u=a[j].u;//删除这一行中含一的数
a[a[j].u].d=a[j].d;
s[a[j].lie]--; //这列含一的数减减
}
}
}
如何回溯时重新链接链表
需要用到的其实只是一种比较高端的链表操作首先先要明白的是普通双向链表的删除操作。
普通双向链表的删除 而只要细细观察就可以发现，其实虽然我们把中间这个数据删除了，但是中间的这个数据却还连着前面的与后面的数据地址，那么我们就可以有中间这个数的前后地址重新连接三个数据。
如何回溯
学会了上面的链表回溯其实就十分简单了，我们只需要按上面的删除操作的思路变成重连链表即可。
回溯函数
void resume(int num)//恢复所在列中有一的行
{
a[a[num].r].l=num;
a[a[num].l].r=num;
for(int i=a[num].d;i!=num;i=a[i].d)//回溯行
{
for(int j=a[i].r;j!=i;j=a[j].r)//回溯列
{
a[a[j].d].u=j;//恢复当前行
a[a[j].u].d=j;
s[a[j].lie]++; //列上元素加一
}
}
}
如何搜索
其实完成了前面的所有操作之后就十分简单了，只需要按照思路先选择含一最少的一列，然后一行一行的去看是不是选他，如果是就输出，不是就回溯就行了。
深度优先搜索函数
void dfs()
{
//行链表中所有元素都已删除，找到可行解
if(a[head].r==head)
{
for(int i=1;i<=ans[0];i++) cout<<ans[i]<<" ";
exit(0);
}
int minn=INT_MAX,c;//找到含一最少的边
for(int i=a[head].l;i!=head;i=a[i].l)
{
if(!s[i]) return;//剪枝
if(s[i]<minn)
{
minn=s[i];
c=i;
}
}
del(c);//删除c列
for(int i=a[c].d;i!=c;i=a[i].d)
{
ans[0]++;
ans[ans[0]]=a[i].hang;//选择一行
//删除行中有一的列
for(int j=a[i].r;j!=i;j=a[j].r)
{
del(a[j].lie);
}
dfs();
ans[0]--;
//恢复所有与当前已有矛盾的行
for(int j=a[i].l;j!=i;j=a[j].l) resume(a[j].lie);
}
resume(c);//还原
return;
}
完整代码
#include<bits/stdc++.h>
using namespace std;
int s[114514],l[114514],r[114514],d[114514],u[114514],col[114514],row[114514],ans[114514],n,m,finded,head,cnt;
void del(int num){
l[r[num]]=l[num];
r[l[num]]=r[num];
for(int i=d[num];i!=num;i=d[i])
for(int j=l[i];j!=i;j=l[j]){
u[d[j]]=u[j];
d[u[j]]=d[j];
s[col[j]]--;
}
}
void resume(int num){
l[r[num]]=num;
r[l[num]]=num;
for(int i=d[num];i!=num;i=d[i])
for(int j=l[i];j!=i;j=l[j]){
u[d[j]]=j;
d[u[j]]=j;
s[col[j]]++;
}
}
void dfs(){
if(r[head]==head){
finded=1;
return;
}
int smin=1e9,c=-1;
for(int i=r[head];i!=head;i=r[i]){
if(!s[i]) return ;
if(s[i]<smin){
smin=s[i];
c=i;
}
}
del(c);
for(int i=d[c];i!=c;i=d[i]){
ans[++ans[0]]=row[i];
for(int j=r[i];j!=i;j=r[j]) del(col[j]);
dfs();
if(finded) return;
ans[0]--;
for(int j=r[i];j!=i;j=r[j]) resume(col[j]);
}
resume(c);
}
void build(){
cin>>n>>m;
for(int i=0;i<=m;i++){
s[i]=0;
l[i]=i-1;
r[i]=i+1;
u[i]=i;
d[i]=i;
}
l[0]=m;
r[m]=0;
cnt=m+1;
for(int i=1;i<=n;i++){
int begin,end,x;
begin=cnt;
end=cnt;
for(int j=1;j<=m;j++){
cin>>x;
if(x==0) continue;
s[j]++;
row[cnt]=i;
col[cnt]=j;
d[u[j]]=cnt;
u[cnt]=u[j];
d[cnt]=j;
u[j]=cnt;
l[cnt]=end;
r[cnt]=begin;
r[end]=cnt;
l[begin]=cnt;
end=cnt;
cnt++;
}
}
}
signed main(){
build();
dfs();
if(!finded) cout<<"No Solution!";
else for(int i=1;i<=ans[0];i++) cout<<ans[i]<< " ";
return 0;
}