首页 > 代码库 > POJ 1084

POJ 1084

2024-07-19 11:53:30   222人阅读

WA了好久，第一次用重覆盖的模型做题。感觉这题有个陷阱，那就是当去掉某些边后，若因为这个边去掉而被破环的正方形还存在，那么就会造成覆盖不完全，WA.

所以，在去掉边后，必定有些正方形是不存在的，须重新计算。另外，计算一个正方形有哪些边也很困难。

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int Maxn=100;const int Maxr=100;const int Maxnode=10000;const int inf=(1<<30);bool vis[Maxn];bool ls[Maxr][Maxn];int L[Maxnode], R[Maxnode], D[Maxnode], U[Maxnode], C[Maxnode];int S[Maxn], H[Maxr], size;	//²»ÐèÒªSÓòvoid Link(int r, int c){    S[c]++; C[size]=c;    U[size]=U[c]; D[U[c]]=size;    D[size]=c; U[c]=size;    if(H[r]==-1) H[r]=L[size]=R[size]=size;    else {        L[size]=L[H[r]]; R[L[H[r]]]=size;        R[size]=H[r]; L[H[r]]=size;    }    size++;}void remove(int c){    for (int i=D[c]; i!=c; i=D[i])        L[R[i]]=L[i], R[L[i]]=R[i];}void resume(int c){    for (int i=U[c]; i!=c; i=U[i])        L[R[i]]=R[L[i]]=i;}int h(){	//Óþ«È·¸²¸ÇÈ¥¹ÀËã¼ôÖ¦    int ret=0;    bool vist[Maxn];    memset (vist, false, sizeof(vist));    for (int i=R[0]; i; i=R[i])    {        if(vist[i])continue;        ret++;        vist[i]=true;        for (int j=D[i]; j!=i; j=D[j])            for (int k=R[j]; k!=j; k=R[k])                vist[C[k]]=true;    }    return ret;}int ans;void Dance(int k){                //¸ù¾Ý¾ßÌåÎÊÌâÑ¡ÔñÏÞÖÆËÑË÷Éî¶È»òÖ±½ÓÇó½â¡£    if(k+h()>=ans) return;    if(!R[0]){        if(k<ans)ans=k;        return;    }    int c=R[0];    for (int i=R[0]; i; i=R[i])        if(S[i]<S[c])c=i;    for (int i=D[c]; i!=c; i=D[i]){        remove(i);        for (int j=R[i]; j!=i; j=R[j])            remove(j);        Dance(k+1);        for (int j=L[i]; j!=i; j=L[j])            resume(j);        resume(i);    }    return ;}void initL(int x){	//col is 1~x,row start from 1    for (int i=0; i<=x; ++i){        S[i]=0;        D[i]=U[i]=i;        L[i+1]=i; R[i]=i+1;    }	//¶ÔÁбíÍ·³õʼ»¯    R[x]=0;    size=x+1;	//ÕæÕýµÄÔªËØ´Óm+1¿ªÊ¼    memset (H, -1, sizeof(H));    ans=inf;    	//markÿ¸öλÖõÄÃû×Ö}bool check(int i,int j,int si,int n){	for(int k=0;k<si;k++){		if(vis[(i-1)*(2*n+1)+j+k]) return false; 		if(vis[(i-1+si)*(2*n+1)+j+k]) return false;  		if(vis[i*n+(i-1)*(n+1)+j+k*(2*n+1)]) return false;   		if(vis[i*n+(i-1)*(n+1)+j+k*(2*n+1)+si]) return false;   	}   	return true;}int main(){	int kase,n; int sof,tmp,tt,c;	scanf("%d",&kase);	while(kase--){	//	sof=0;		scanf("%d",&n);	//	initL(sof);		scanf("%d",&tt);		memset(vis,false,sizeof(vis));		for(int i=1;i<=tt;i++){			scanf("%d",&tmp);			vis[tmp]=true;		}		memset(ls,false,sizeof(ls));		c=1;	    for(int si=1;si<=n;si++){			for(int i=1;i<=n-si+1;i++){   				for(int j=1;j<=n-si+1;j++){   					if(check(i,j,si,n)){					  for(int k=0;k<si;k++){                    	ls[(i-1)*(2*n+1)+j+k][c]=true;                     	ls[(i-1+si)*(2*n+1)+j+k][c]=true;                     	ls[i*n+(i-1)*(n+1)+j+k*(2*n+1)][c]=true;                     	ls[i*n+(i-1)*(n+1)+j+k*(2*n+1)+si][c]=true; 					  } 					   	c++;   					}             	}         	}     	}     	initL(c-1);     	for(int i=1;i<=2*(n)*(n+1);i++){     		for(int j=1;j<c;j++)     		if(ls[i][j])     		Link(i,j);     	}     	Dance(0);     	printf("%d\n",ans);	}	return 0;}

　　

POJ 1084


联系
我们