猫史档案馆

DancingLinks代码~~~

#include <bits/stdc++.h>

using namespace std;

const int N=5511;

int n,m;
int l[N];
int r[N];
int u[N],d[N];
int s[N];
int ro[N],co[N];
int idx;

int ans[N];
int top;

inline void init()
{
    for(int i=0;i<=m;i++)
    {
        l[i]=i-1;
        r[i]=i+1;
        u[i]=d[i]=i;
    }
    idx=m+1;
    l[0]=m,r[m]=0;
}

inline void add(int & hh,int & tt,int x,int y)
{
    ro[idx]=x,co[idx]=y,s[y]++;
    u[idx]=y;
    d[idx]=d[y];
    u[d[y]]=idx;
    d[y]=idx;
    
    r[hh]=l[tt]=idx;
    r[idx]=tt;
    l[idx]=hh;
    
    tt=idx++;
}

inline void remove(int p)
{
    r[l[p]]=r[p];
    l[r[p]]=l[p];
    for(int i=d[p];i!=p;i=d[i])
    {
        for(int j=r[i];j!=i;j=r[j])
        {
            s[co[j]]--;
            u[d[j]]=u[j];
            d[u[j]]=d[j];
        }
    }
}

inline void resume(int p)
{
    for(int i=u[p];i!=p;i=u[i])
    {
        for(int j=l[i];j!=i;j=l[j])
        {
            u[d[j]]=j;
            d[u[j]]=j;
            s[co[j]]++;
        }
    }
    r[l[p]]=p;
    l[r[p]]=p;
}

bool dfs()
{
    if(r[0]==0)return 1;
    
    
    int p=r[0];
    for(int i=r[0];i;i=r[i])    
    {
        if(s[i]<s[p])p=i;
    }
    
    
    remove(p);
    for(int i=d[p];i!=p;i=d[i])
    {
        ans[++top]=ro[i];
        for(int j=r[i];j!=i;j=r[j])remove(co[j]);
        if(dfs())return 1;
        for(int j=l[i];j!=i;j=l[j])resume(co[j]);
        top--;
    }
    resume(p);
    return 0;
}

int main()
{
    cin>>n>>m;
    init();
    for(int i=1;i<=n;i++)
    {
        int hh,tt;
        hh=tt=idx;
        for(int j=1;j<=m;j++)
        {
            int x;
            scanf("%d",&x);
            if(x)add(hh,tt,i,j);
        }
    }
    if(dfs())
    {
        for(int i=1;i<=top;i++)
        {
            printf("%d ",ans[i]);
        }
    }else
    {
        puts("No Solution!");
    }
    return 0;
}