舞蹈链学习笔记

受到neyc_jiamao的强迫，我必须做这个笔记（大哭）

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=270000;
int n,m,l[maxn],r[maxn],u[maxn],d[maxn],h[maxn],col[maxn],row[maxn];
int s[maxn],ans[maxn],tot=0;
void init(){
    int i;
    for(i=0;i<=m;i++){
        l[i]=i-1;r[i]=i+1;
        u[i]=d[i]=i;
    }r[m]=0,l[0]=m;
    memset(h,-1,sizeof(h));
    memset(s,0,sizeof(s));
    tot=m+1;
}
void cr(int x,int y){
    s[y]++;
    row[tot]=x;col[tot]=y;
    u[tot]=y;d[tot]=d[y];
    u[d[y]]=tot;
    d[y]=tot;
    if(h[x]==-1)h[x]=r[tot]=l[tot]=tot;
    else{
        r[tot]=h[x];
        l[tot]=l[h[x]];
        r[l[h[x]]]=tot;
        l[h[x]]=tot;
    }tot++;
}
void sc(int x){
    int i,j;
    r[l[x]]=r[x];l[r[x]]=l[x];
    for(i=d[x];i!=x;i=d[i]){
        for(j=r[i];j!=i;j=r[j]){
            u[d[j]]=u[j];
            d[u[j]]=d[j];
            s[col[j]]--;
        }
    }
}
void hf(int x){
    int i,j;
    for(i=u[x];i!=x;i=u[i]){
        for(j=l[i];j!=i;j=l[j]){
        u[d[j]]=j;
        d[u[j]]=j;
        s[col[j]]++;}
    }r[l[x]]=x;l[r[x]]=x;
}
bool gogo(int dp){
    int i,j;
    if(r[0]==0){
        for(i=0;i<dp;i++)printf("%d ",ans[i]);;
        return 1;
    }
    int c=r[0];
    for(i=r[0];i!=0;i=r[i])if(s[i]<s[c])c=i;
    sc(c);
    for(i=d[c];i!=c;i=d[i]){
        ans[dp]=row[i];
        for(j=r[i];j!=i;j=r[j])sc(col[j]);
        if(gogo(dp+1))return 1;
        for(j=l[i];j!=i;j=l[j])hf(col[j]);
    }hf(c);
    return 0;
}
int main(){
    //freopen("dlx.in","r",stdin);
    //freopen("dlx.out","w",stdout);
    int i,j,ls;
    scanf("%d%d",&n,&m);
    init();
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
            scanf("%d",&ls);
            if(ls)cr(i,j);
        }
    if(!gogo(0))cout<<"No Solution!";
    return 0;
}