代码

struct DLX{    int n,id;    int L[maxn],R[maxn],U[maxn],D[maxn];    int C[maxn],S[maxn],loc[maxn][2];    int H[ms];    void init(int nn=0) //传列长    {        n=nn;        for(int i=0;i<=n;i++) U[i]=D[i]=i,L[i]=i-1,R[i]=i+1;        L[0]=n; R[n]=0;        id=n;        memset(S,0,sizeof(S));        memset(H,-1,sizeof(H));    }    void Link(int x,int y)    {        ++id;        D[id]=y; U[id]=U[y];        D[U[y]]=id; U[y]=id;        loc[id][0]=x,loc[id][1]=y;        C[id]=y; S[y]++;        if(H[x]==-1) H[x]=L[id]=R[id]=id;        else        {            int a=H[x];            int b=R[a];            L[id]=a; R[a]=id;            R[id]=b; L[b]=id;            H[x]=id;        }    }    void Remove(int c)    {        L[R[c]]=L[c];        R[L[c]]=R[c];        for(int i=D[c];i!=c;i=D[i])            for(int j=R[i];j!=i;j=R[j])        {            U[D[j]]=U[j];            D[U[j]]=D[j];            S[C[j]]--;        }    }    void Resume(int c)    {        for(int i=U[c];i!=c;i=U[i])            for(int j=R[i];j!=i;j=R[j])        {            S[C[j]]++;            U[D[j]]=j;            D[U[j]]=j;        }        L[R[c]]=c;        R[L[c]]=c;    }    bool dfs(int step)    {        if(step>=N) return true;        if(R[0]==0) return false;        int Min=INF,c=-1;        for(int i=R[0];i;i=R[i])            if(Min>S[i]){ Min=S[i]; c=i; }        Remove(c);        for(int i=D[c];i!=c;i=D[i])        {            //ans[step]=loc[i][0];            for(int j=R[i];j!=i;j=R[j]) Remove(C[j]);            if(dfs(step+1)) return true;            for(int j=L[i];j!=i;j=L[j]) Resume(C[j]);        }        Resume(c);        return false;    }}dlx;