【POJ 3740】Easy Finding DLX(Dancing Links)精密カバー問題
3752 ワード
题意:多组のデータ、各组のデータはあなたに何行の数をあげて、その中の何行を选ぶことを要求して、各列がすべてあってしかも1つだけあるようにして、寻ねるのは実行することができなくて、あるいは探し出すことができますか.
标题:1、暴挙捜査.2、DLX(Dancing links).
本文はDLXを書いた.アルゴリズムは白書P 406またはhttp://www.cnblogs.com/grenet/p/3145800.html
細かいことを言いますが、削除操作の形は
|
——|————
——|————
——|————
削除されたポイント同士の連絡は削除せずに保持できます.正確にはこれらの点を削除したのではなく、この形を削除したのです.
また、回復するときは逆に回復しなければなりません.
まず、どのカラムから削除するかを決定し、removeを1回行い、そのカラムの各行を列挙し、removeを行い、dfsを行い、resumeを行います.ループから飛び出したときにresumeでカラムを決定します.
コードを添付して、とてもきれいだと思います.少し辛抱強くしてください.ネット上の他の人より絶対に読みやすいことを保証します.
ああ、そうだ、点、行、列の単独のremoveとresume関数を書く必要はありません.それは馬鹿すぎて、テンプレートを書く必要もありません.これは永遠に使えないと思います...
福祉を与える.
出力デバッガ専用です.
もちろん、あなたは行列を作って単独で操作しなければなりません.私も止めません.
それからデータは貼らないで、直接3740 discussを見に行きましょう.2組あります.
标题:1、暴挙捜査.2、DLX(Dancing links).
本文はDLXを書いた.アルゴリズムは白書P 406またはhttp://www.cnblogs.com/grenet/p/3145800.html
細かいことを言いますが、削除操作の形は
|
——|————
——|————
——|————
削除されたポイント同士の連絡は削除せずに保持できます.正確にはこれらの点を削除したのではなく、この形を削除したのです.
また、回復するときは逆に回復しなければなりません.
まず、どのカラムから削除するかを決定し、removeを1回行い、そのカラムの各行を列挙し、removeを行い、dfsを行い、resumeを行います.ループから飛び出したときにresumeでカラムを決定します.
コードを添付して、とてもきれいだと思います.少し辛抱強くしてください.ネット上の他の人より絶対に読みやすいことを保証します.
ああ、そうだ、点、行、列の単独のremoveとresume関数を書く必要はありません.それは馬鹿すぎて、テンプレートを書く必要もありません.これは永遠に使えないと思います...
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 400
#define NN 10000
using namespace std;
struct DLX
{
int U[NN],D[NN],L[NN],R[NN],C[NN];
int H[NN],T[NN],cnt;
inline void init(int m)
{
cnt=0;
memset(H,0,sizeof(H));
for(cnt=0;cnt<=m;cnt++)
{
U[cnt]=D[cnt]=C[cnt]=cnt;
L[cnt]=cnt-1,R[cnt]=cnt+1;
}
L[0]=--cnt,R[cnt]=0;
}
inline void newnode(int x,int y)
{
C[++cnt]=y;T[y]++;
if(!H[x])H[x]=L[cnt]=R[cnt]=cnt;
else L[cnt]=H[x],R[cnt]=R[H[x]];
R[H[x]]=L[R[H[x]]]=cnt,H[x]=cnt;
U[cnt]=U[y],D[cnt]=y;
U[y]=D[U[y]]=cnt;
}
inline void scan(int n,int m)
{
int i,j,k;
for(i=1;i<=n;i++)for(j=1;j<=m;j++)
{
scanf("%d",&k);
if(k)newnode(i,j);
}
}
inline void remove(int x)
{
for(int i=D[x];i!=x;i=D[i])
{
for(int j=R[i];j!=i;j=R[j])
{
U[D[j]]=U[j];
D[U[j]]=D[j];
T[C[j]]--;
}
}
L[R[x]]=L[x];
R[L[x]]=R[x];
}
inline void resume(int x)
{
for(int i=U[x];i!=x;i=U[i])
{
for(int j=L[i];j!=i;j=L[j])
{
U[D[j]]=j;
D[U[j]]=j;
T[C[j]]++;
}
}
L[R[x]]=x;
R[L[x]]=x;
}
inline bool dfs()
{
if(!R[0])return true;
int S=R[0],W=T[S],i,j;
for(i=R[S];i;i=R[i])if(T[i]<W)
{
W=T[i];
S=i;
}
remove(S);
for(i=D[S];i!=S;i=D[i])
{
for(j=R[i];j!=i;j=R[j])remove(C[j]);
if(dfs())return true;
for(j=L[i];j!=i;j=L[j])resume(C[j]);
}
resume(S);
return false;
}
}dlx;
int main()
{
// freopen("test.in","r",stdin);
// freopen("my.out","w",stdout);
int n,m;
while(~scanf("%d%d",&n,&m))
{
dlx.init(m);
dlx.scan(n,m);
if(dlx.dfs())puts("Yes, I found it");
else puts("It is impossible");
}
return 0;
}
福祉を与える.
出力デバッガ専用です.
inline void print_line(int x)
{
int i=x;
do{
printf("%d->",i);
i=R[i];
}while(i!=x);
puts("");
}
inline void print_list(int x)
{
int i=x;
do{
printf("%d->",i);
i=D[i];
}while(i!=x);
puts("");
}
inline void print(int x)
{
int i=x;
do{
print_list(i);
puts("|");
i=R[i];
}while(i!=x);
puts("");
puts("");
}
もちろん、あなたは行列を作って単独で操作しなければなりません.私も止めません.
inline void remove_point(int x)
{
D[U[x]]=D[x];
U[D[x]]=U[x];
R[L[x]]=R[x];
L[R[x]]=L[x];
}
inline void resume_point(int x)
{
D[U[x]]=x;
U[D[x]]=x;
R[L[x]]=x;
L[R[x]]=x;
}
inline void remove_line(int x)
{
int i=x;
do{
U[D[i]]=U[i];
D[U[i]]=D[i];
i=R[i];
}while(i!=x);
}
inline void resume_line(int x)
{
int i=x;
do{
U[D[i]]=i;
D[U[i]]=i;
i=L[i];
}while(i!=x);
}
inline void remove_list(int x)
{
int i=x;
do{
R[L[i]]=R[i];
L[R[i]]=L[i];
i=D[i];
}while(i!=x);
}
inline void resume_list(int x)
{
int i=x;
do{
R[L[i]]=i;
L[R[i]]=i;
i=U[i];
}while(i!=x);
}
それからデータは貼らないで、直接3740 discussを見に行きましょう.2組あります.