洛谷P1074 靶形數獨（NOIp2009）

DLX

題目傳送門

正常方法是DFS+一些剪枝。但是因為這是數獨，可以用DLX求出數獨的所有解，取分數最大的那個即可。

不會DLX的小夥伴看這裡

代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 81*9
#define M 81*4
using namespace std;
struct node{
    node *l,*r,*u,*d;
    int x,y;
}c[M+],a[N*M+],s,*null=&s,*h;
int cnt[M+],mp[][],ans[][],id[N+][M+],n=N,m=M,nd,res;
bool f[N+][M+];
int w[][]=
    {{,,,,,,,,,},
    {,,,,,,,,,},
    {,,,,,,,,,},
    {,,,,,,,,,},
    {,,,,,,,,,},
    {,,,,,,,,,},
    {,,,,,,,,,},
    {,,,,,,,,,},
    {,,,,,,,,,},
    {,,,,,,,,,}};
void nsrt(int x,int y,int z){
    int i=(x-)*9+y,j=(i-)*9+z;
    f[j][(x-)*9+z]=true;
    f[j][+(y-)*9+z]=true;
    int k=((x-)/*3+(y-)/)+;
    f[j][+(k-)*9+z]=true;
    f[j][+i]=true;
}
void build(){
    for (int i=;i<=;i++)
        for (int j=;j<=;j++)
            if (!mp[i][j]) for (int k=;k<=;k++) nsrt(i,j,k);
            else nsrt(i,j,mp[i][j]);
    h=&c[],h->d=h->u=h->l=h->r=h,h->x=h->y=; node *pre=h;
    for (int i=;i<=m;i++){
        node *p=&c[i]; p->u=p->d=p,p->x=,p->y=i;
        p->r=pre->r,p->l=pre,pre->r->l=p,pre->r=p,pre=p;
    }
    for (int i=;i<=n;i++)
        for (int j=;j<=m;j++)
            if (f[i][j]){
                a[id[i][j]=++nd].x=i,a[nd].y=j;
                a[nd].l=a[nd].r=a[nd].u=a[nd].d=&a[nd];
            }
    for (int j=;j<=m;j++){
        node *pre=&c[j];
        for (int i=;i<=n;i++)
            if (f[i][j]){
                cnt[j]++; node *p=&a[id[i][j]];
                p->d=pre->d,p->u=pre,pre->d->u=p,pre->d=p,pre=p;
            }
    }
    for (int i=;i<=n;i++){
        node *pre=null;
        for (int j=;j<=m;j++)
            if (f[i][j])
                if (pre==null) pre=&a[id[i][j]];
                else{
                    node *p=&a[id[i][j]]; p->r=pre->r;
                    p->l=pre,pre->r->l=p,pre->r=p,pre=p;
                }
    }
}
void rmv(int x){
    node *p=&c[x],*p1=p->d;
    p->l->r=p->r,p->r->l=p->l;
    while (p1!=p){
        node *p2=p1->r;
        while (p2!=p1)
            p2->d->u=p2->u,p2->u->d=p2->d,cnt[p2->y]--,p2=p2->r;
        p1=p1->d;
    }
}
void rsm(int x){
    node *p=&c[x],*p1=p->d;
    p->l->r=p->r->l=p;
    while (p1!=p){
        node *p2=p1->r;
        while (p2!=p1)
            p2->d->u=p2->u->d=p2,cnt[p2->y]++,p2=p2->r;
        p1=p1->d;
    }
}
node *find(){
    node *p=h->r,*ans=h->r; int mn=;
    while (p!=h){
        if (cnt[p->y]<mn) mn=cnt[p->y],ans=p;
        p=p->r;
    }
    return ans;
}
//上面都是闆子
void calc(){//計算分數
    int ret=;
    for (int i=;i<=;i++)
        for (int j=;j<=;j++)
            ret+=w[i][j]*ans[i][j];
    res=max(res,ret);
}
void dfs(){
    if (h->r==h) return calc();
    node *p=find(),*p1=p->d;
    if (p1==p) return; rmv(p->y);
    while (p1!=p){
        ans[(p1->x-)/+][((p1->x-)/)%9+]=(p1->x-)%9+;
        node *p2=p1->r;
        while (p2!=p1) rmv(p2->y),p2=p2->r;
        dfs(),p2=p1->l;
        while (p2!=p1) rsm(p2->y),p2=p2->l;
        p1=p1->d;
    }
    return rsm(p->y);
}
int main(){
    for (int i=;i<=;i++)
        for (int j=;j<=;j++)
            scanf("%d",&mp[i][j]);
    build(),res=-,dfs();
    printf("%d\n",res);
}