hdu 3529(DLX)
重复点覆盖的题, 建好图就可以直接A 了。。。
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 497Accepted Submission(s): 276
#include <stdio.h> #include <string.h> #include <iostream> using namespace std; #define N 100000 #define INF 0x3ffffff int n,m; int U[N],D[N],R[N],L[N],num[N],H[N],col[N],line[N]; int nn,mm; char g[20][20]; int tg[20][20]; int head,id,mi; int up[4]={1,-1,0,0}; int rl[4]={0,0,1,-1}; void prepare() { for(int i=0;i<=mm;i++) { num[i]=0; D[i]=i; U[i]=i; R[i]=i+1; L[i+1]=i; } R[mm]=0; L[0]=mm; memset(H,-1,sizeof(H)); } void link(int tn,int tm) { id++; num[ line[id]=tm ]++; col[id]=tn; U[D[tm]]=id; D[id]=D[tm]; D[tm]=id; U[id]=tm; if(H[tn]<0) H[tn]=R[id]=L[id]=id; else { L[R[H[tn]]]=id; R[id]=R[H[tn]]; L[id]=H[tn]; R[H[tn]]=id; } } void build() { id=mm; prepare(); for(int i=1;i<n-1;i++) for(int j=1;j<m-1;j++) { int flag=0; if(g[i][j]=='.') { for(int i1=0;i1<4;i1++) { int ti=i,tj=j; ti+=up[i1]; tj+=rl[i1]; while( g[ti][tj]!='*' ) { if(g[ti][tj]=='#') { flag=1; link(nn,tg[ti][tj]); break; } ti+=up[i1]; tj+=rl[i1]; } } } if(flag==1) nn++; } } void remove(int s) { for(int i=D[s];i!=s;i=D[i]) { R[L[i]]=R[i]; L[R[i]]=L[i]; } } void resume(int s) { for(int i=D[s];i!=s;i=D[i]) R[L[i]]=L[R[i]]=i; } int h() { int mark[33]; memset(mark,0,sizeof(mark)); int sum=0; for(int i=R[head];i!=head;i=R[i]) { if(mark[i]==0) { sum++; mark[i]=1; for(int j=D[i];j!=i;j=D[j]) for(int k=R[j];k!=j;k=R[k]) mark[line[k]]=1; } } return sum; } void dfs(int s) { if(s+h()>=mi) return ; if(R[head]==head) { mi=s; return ; } int tmi=INF,tu; for(int i=R[head];i!=head;i=R[i]) if(num[i]<tmi) { tmi=num[i]; tu=i; } for(int i=D[tu];i!=tu;i=D[i]) { remove(i); for(int j=R[i];j!=i;j=R[j]) { remove(j); } dfs(s+1); for(int j=L[i];j!=i;j=L[j]) resume(j); resume(i); } } int main() { while(scanf("%d%d",&n,&m)!=EOF) { head=0; for(int i=0;i<n;i++) scanf("%s",g[i]); nn=1; mm=0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { if(g[i][j]=='#') { mm++; tg[i][j]=mm; } } build(); mi=INF; dfs(0); printf("%d\n",mi); } return 0; }优质内容筛选与推荐>>