hust 1017 DLX

#include<set>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pb push_back
#define mp make_pair
#define Maxn 1000010
#define Maxm 80002
#define LL __int64
#define Abs(x) ((x)>0?(x):(-x))
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define inf 100000
#define lowbit(x) (x&(-x))
#define Mod 1000000007
using namespace std;
int U[Maxn],D[Maxn],R[Maxn],L[Maxn],C[Maxn],S[Maxn],X[Maxn],H[],Q[],id;
void init(int m)
{
int i;
for(i=;i<=m;i++){
D[i]=U[i]=i;
L[i+]=i;
R[i]=i+;
S[i]=;
}
R[m]=;
id=m+;
}
void ins(int r,int c)
{
D[id]=D[c];
U[id]=c;
U[D[c]]=id;
D[c]=id;
S[c]++;
if(H[r]<)
H[r]=L[id]=R[id]=id;
else{
L[id]=H[r];
R[id]=R[H[r]];
L[R[H[r]]]=id;
R[H[r]]=id;
}
C[id]=c;
X[id++]=r;
}
void Remove(int c)
{
int i,j;
R[L[c]]=R[c];
L[R[c]]=L[c];
for(i=D[c];i!=c;i=D[i]){
for(j=R[i];j!=i;j=R[j]){
D[U[j]]=D[j];
U[D[j]]=U[j];
S[C[j]]--;
}
}
}
void Resume(int c)
{
int i,j;
R[L[c]]=c;
L[R[c]]=c;
for(i=D[c];i!=c;i=D[i]){
for(j=R[i];j!=i;j=R[j]){
U[D[j]]=j;
D[U[j]]=j;
S[C[j]]++;
}
}
}
bool dfs(int k)
{
int i,j,c,temp;
if(R[]==){
printf("%d",k);
for(i=;i<k;i++){
printf(" %d",X[Q[i]]);
}
printf("\n");
return true;
}
temp=inf;
for(i=R[];i;i=R[i]){
if(S[i]<temp){
temp=S[i];
c=i;
}
}
Remove(c);
for(i=D[c];i!=c;i=D[i]){
Q[k]=i;
for(j=R[i];j!=i;j=R[j])
Remove(C[j]);
if(dfs(k+))
return true;
for(j=L[i];j!=i;j=L[j])
Resume(C[j]);
} Resume(c);
return false;
}
int main()
{
int n,m,i,j,k,x;
while(scanf("%d%d",&n,&m)!=EOF){
init(m);
for(i=;i<=n;i++){
scanf("%d",&k);
H[i]=-;
while(k--){
scanf("%d",&x);
ins(i,x);
}
}
if(!dfs())
printf("NO\n");
}
return ;
}

思路:裸的精确覆盖

上一篇:.net学习笔记----WebConfig常用配置节点介绍


下一篇:html和css