首页 > 代码库 > bzoj 2706: [SDOI2012]棋盘覆盖 Dancing Link

bzoj 2706: [SDOI2012]棋盘覆盖 Dancing Link

2706: [SDOI2012]棋盘覆盖

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 255  Solved: 77
[Submit][Status]

Description

在一个N*M个方格组成的棋盘内,有K个方格被称为特殊方格。我们要使用一组俄罗斯方块来覆盖这个棋盘,保证特殊方格不能被覆盖,非特殊方格只能被一个俄罗斯方块覆盖,求最多能容纳的俄罗斯方块的数量。
已知有以下三组俄罗斯方块,一个棋盘可能用其中的某一组。
 

Input

第一行三个整数,N,M,K,和一个字符,type,为所用的俄罗斯方块组。

接下来K行每行两个整数,X,Y,表示第X行第Y列为特殊方格。

 

Output

一个整数,为所求的答案。

【样例输入1

8 8 0 A

【样例输出1

32

【样例输入2

7 6 6 C

3 1

3 6

5 3

5 4

5 7

6 7

【样例输出2

12

【数据范围】

 

测试点

N,M

K

type

[1, 6]

0 < N,M <= 100

0<=K<=N*M

A

[7, 12]

N=M=2^L,0<L<=200000

K=1

B

[13, 20]

0<N,M<=11

0<=K<=N*M

C

 

  第一组:二分图匹配

  第二组:可以通过分治法证明ans=(n*n-1)/3

  第三组:我用的是Dancing Link,但是不知道有没有网络流解法,如果用dancing link那么要注意如果当前答案等于(n*m-k)/3就强制退出。

 

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;namespace sec1{        const int maxe=21000;        const int maxv=11000;        const int maxn=102;        const int mov[4][2]={{1,0},{-1,0},{0,-1},{0,1}};        struct Edge        {                int np,val;                Edge *next;        }E[maxe],*V[maxv];        int tope=-1;        bool bad[maxn][maxn];        void addedge(int x,int y)        {                E[++tope].np=y;                E[tope].next=V[x];                V[x]=&E[tope];        }        bool vis[maxn*maxn];        int ptr[maxn*maxn];        bool find(int now)        {                Edge *ne;                for (ne=V[now];ne;ne=ne->next)                {                        if (vis[ne->np])continue;                        vis[ne->np]=true;                        if (!ptr[ne->np] || find(ptr[ne->np]))                        {                                ptr[ne->np]=now;                                return true;                        }                }                return false;        }        int main(int n,int m,int t)        {                int i,j,k,x,y;                for (i=0;i<t;i++)                {                        scanf("%d%d",&x,&y);                        bad[x][y]=true;                }                for (i=1;i<=n;i++)                {                        for (j=1;j<=m;j++)                        {                                if (bad[i][j] || ((i+j)&1))continue;                                for (k=0;k<4;k++)                                {                                        if (i+mov[k][0]>0 && i+mov[k][0]<=n                                                         && j+mov[k][1]>0 && j+mov[k][1]<=m                                                        && !bad[i+mov[k][0]][j+mov[k][1]])                                        {                                                addedge(i*m+j,(i+mov[k][0])*m+j+mov[k][1]);                                        }                                }                        }                }                int ans=0;                for (i=1;i<=n;i++)                {                        for (j=1;j<=m;j++)                        {                                if ((i+j)%2==0)                                {                                        memset(vis,0,sizeof(vis));                                        ans+=find(i*m+j);                                }                        }                }                printf("%d\n",ans);                return 0;        }}namespace sec2{        const int maxn=1100000;        int a[maxn];        long long b[maxn];        void main(const char* str)        {                int m=strlen(str);                for (int i=0;i<m;i++)                        a[(m-i-1)/8]=a[(m-i-1)/8]*10+str[i]-0;                int n=(m-1)/8;                for (int i=0;i<=n;i++)                        for (int j=0;j<=n;j++)                        {                                b[i+j]+=(long long)a[i]*a[j];                                b[i+j+1]+=b[i+j]/100000000;                                b[i+j]%=100000000;                        }                for (int i=0;i<n*2+10;i++)                {                        b[i+1]+=b[i]/100000000;                        b[i]%=100000000;                }                n=n*2+10;                while (!b[n])n--;                b[0]--;                for (int i=n;i>=0;i--)                {                        b[i-1]+=b[i]%3*100000000;                        b[i]/=3;                }                while (!b[n])n--;                printf("%lld",b[n]);                for (int i=n-1;i>=0;i--)                        printf("%08lld",b[i]);                printf("\n");        }}namespace sec3//DLX{        //{{{        const int maxn=12;        const int maxd=maxn*maxn*4*4;        const int mov[4][2]={{1,0},{-1,0},{0,-1},{0,1}};        const int inf=0x3f3f3f3f;        int L[maxd],R[maxd],D[maxd],U[maxd];        bool bad[maxn][maxn];        int tt[maxd];        int top[maxd];        int head[maxn*maxn];        int vec[4];        int ans=0,cnt=0;        int topd=0;        int anslim;        void Init_DLX(int l)        {                int now;                L[0]=R[0]=D[0]=U[0]=0;                for (int i=1;i<=l;i++)                {                        now=++topd;                        R[now]=head[0];                        L[now]=L[head[0]];                        U[now]=D[now]=now;                        L[R[now]]=now;                        R[L[now]]=now;                        top[now]=i;                        head[i]=now;                }        }        void Add_DLX(int *ss)        {                int now=++topd;                D[now]=head[0];                U[now]=U[head[0]];                L[now]=R[now]=now;                D[U[now]]=now;                U[D[now]]=now;                int h0=now;                while (~(*ss))                {                        now=++topd;                        D[now]=head[*ss];                        U[now]=U[head[*ss]];                        L[now]=L[h0];                        R[now]=h0;                        U[D[now]]=now;                        D[U[now]]=now;                        R[L[now]]=now;                        L[R[now]]=now;                        top[now]=*ss;                        tt[*ss]++;                        ss++;                }        }        void Cover(int c)        {                R[L[c]]=R[c];                L[R[c]]=L[c];                for (int i=D[c];i!=c;i=D[i])                {                        for (int j=R[i];j!=i;j=R[j])                        {                                tt[top[j]]--;                                U[D[j]]=U[j];                                D[U[j]]=D[j];                        }                }        }        void Resume(int c)        {                R[L[c]]=c;                L[R[c]]=c;                for (int i=D[c];i!=c;i=D[i])                {                        for (int j=R[i];j!=i;j=R[j])                        {                                tt[top[j]]++;                                U[D[j]]=D[U[j]]=j;                        }                }        }        void Search_DLX(int tot)        {                ans=max(ans,tot);                if (ans==anslim)return;                int bst=inf,bstid;                bstid=R[head[0]];                for (int i=R[head[0]];i!=head[0];i=R[i])                        if (tt[top[i]] && tt[top[i]]<bst)                                bst=tt[top[i]],bstid=top[i];                for (int i=D[head[bstid]];i!=head[bstid];i=D[i])                {                        int k;                        for (k=R[i];top[k];k=R[k]);                        for (int j=R[k];j!=k;j=R[j])Cover(head[top[j]]);                        Search_DLX(tot+1);                        for (int j=R[k];j!=k;j=R[j])Resume(head[top[j]]);                }        }        void main(int n,int m,int t)        {                int i,j,k1,k2;                vec[3]=-1;                int x,y;                for (i=0;i<t;i++)                {                        scanf("%d%d",&x,&y);                        bad[x][y]=true;                }                anslim=(n*m-t)/3;                Init_DLX((n+1)*m);                for (i=1;i<=n;i++)                {                        for (j=1;j<=m;j++)                        {                                if (bad[i][j])continue;                                for (k1=0;k1<4;k1++)                                {                                        if (i+mov[k1][0]==0 || i+mov[k1][0]==n+1                                                        || j+mov[k1][1]==0 || j+mov[k1][1]==m+1                                                        || bad[i+mov[k1][0]][j+mov[k1][1]])                                                continue;                                        for (k2=k1+1;k2<4;k2++)                                        {                                                if (i+mov[k2][0]==0 || i+mov[k2][0]==n+1                                                                || j+mov[k2][1]==0 || j+mov[k2][1]==m+1                                                                || bad[i+mov[k2][0]][j+mov[k2][1]])                                                        continue;                                                vec[0]=i*m+j;                                                vec[1]=(i+mov[k2][0])*m+j+mov[k2][1];                                                vec[2]=(i+mov[k1][0])*m+j+mov[k1][1];                                                Add_DLX(vec);                                        }                                }                        }                }                Search_DLX(0);                printf("%d\n",ans);        }        //}}}}char str[110000];int main(){        freopen("input.txt","r",stdin);        freopen("output.txt","w",stdout);        int n,m,t;        char type;        scanf("%s %d %d %c\n",str,&m,&t,&type);        if (type==A)        {                sscanf(str,"%d",&n);                sec1::main(n,m,t);        }else if (type==B)        {                sec2::main(str);        }else if (type==C)        {                sscanf(str,"%d",&n);                sec3::main(n,m,t);        }}

 

bzoj 2706: [SDOI2012]棋盘覆盖 Dancing Link