首页 > 代码库 > HDU 3957 Street Fighter（搜索、DLX、重复覆盖+精确覆盖）
HDU 3957 Street Fighter（搜索、DLX、重复覆盖+精确覆盖）
很久以前就看到的一个经典题，一直没做，今天拿来练手。街霸
给n<=25个角色，每个角色有 1 or 2 个版本（可以理解为普通版以及爆发版），每个角色版本可以KO掉若干人。
问最少选多少个角色（每个角色只能选一次），使得可以KO掉其他所有人（包括所有版本）。
典型的DLX。前∑mode[i]列表示被KO的人版本，重复覆盖。后n列表示选了的人，精确覆盖。
即，在精确覆盖满足的前提下，完成重复覆盖，且使所选行最少。
据说这题可以转化成只用一种覆盖，或者是dfs+剪枝。这里就先这样吧。
加了好多注释，方便以后看。
注意的是，dance的时候，要先删除重复覆盖，再删除精确覆盖。。。
2515MS
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <set>#include <queue>#include <map>using namespace std;#define MP make_pair#define ll long long#define inf 0x3f3f3f3f#define maxr 88#define maxn (maxr*maxr)struct DLX{ int m;// amount of column int m1,m2;// amount of repeat column and exact column int L[maxn],R[maxn],U[maxn],D[maxn],cnt; int row[maxn],col[maxn]; int N[maxr],use[maxr],head[maxr]; void init(int _m){// may need modify this function m = _m; memset(head,-1,sizeof(head)); memset(N,0,sizeof(N)); for(int i=0;i<=m;++i){ L[i]=i-1,R[i]=i+1; U[i]=D[i]=i; row[i]=0,col[i]=i; } L[0]=m,R[m]=0; cnt=m; best = inf; } void exrm(int c){// remove of exact cover, private 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],--N[col[j]]; } void exres(int c){// resume of exact cover, private for(int i=U[c];i!=c;i=U[i]) for(int j=L[i];j!=i;j=L[j]) U[D[j]]=D[U[j]]=j,++N[col[j]]; L[R[c]]=R[L[c]]=c; } void rm(int x){// remove of repeat cover, private for(int i=D[x];i!=x;i=D[i]) L[R[i]]=L[i],R[L[i]]=R[i]; } void res(int x){// resume of repeat cover, private for(int i=D[x];i!=x;i=D[i]) L[R[i]]=R[L[i]]=i; } int low(){// private, sometimes need modify this function int mi=maxr,idx=0; for(int i=R[0];i<=m1;i=R[i])if(N[i]<mi&&N[i])mi=N[i],idx=i; return idx; } void link(int r,int c){ ++N[c],++cnt; row[cnt]=r,col[cnt]=c; U[cnt]=U[c],D[cnt]=c; U[D[cnt]]=D[U[cnt]]=cnt; if(head[r]==-1) head[r]=L[cnt]=R[cnt]=cnt; else { L[cnt]=L[head[r]]; R[cnt]=head[r]; L[R[cnt]]=R[L[cnt]]=cnt; } } bool del[maxr]; int cost2(){// lower_bound int ret=0; memset(del,false,sizeof(del)); for(int c=R[0];c && c<=m1;c=R[c]){ if(!del[c]){ del[c]=true; ret++; for(int i=D[c];i!=c;i=D[i]) for(int j=R[i];j!=i;j=R[j]) del[col[j]]=true; } } return ret; } int best; void dance(int dep,int val){// always need modify this function if(R[0]==0 || R[0]>m1){ best = min(best, val); return ; } int c=low(); if(c==0)return ; if(dep+cost2()>=best) return ; for(int i=D[c];i!=c;i=D[i]){ int r=row[i]; use[dep]=i; rm(i); for(int j=R[i];j!=i;j=R[j]) if(col[j]<=m1) rm(j); for(int j=R[i];j!=i;j=R[j]) if(col[j]>m1) exrm(col[j]); dance(dep+1,val+1); for(int j=L[i];j!=i;j=L[j]) if(col[j]>m1) exres(col[j]); for(int j=L[i];j!=i;j=L[j]) if(col[j]<=m1) res(j); res(i); } }}dlx;int mode[30];int sum[30];vector<pair<int,int> >beat[30][2];int main(){ int t,ca=0; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); for(int i=0;i<n;++i){ scanf("%d",mode+i); if(i==0) sum[i] = mode[i]; else sum[i] = sum[i-1]+mode[i]; for(int j=0;j<mode[i];++j){ int k,beatp,beatm; scanf("%d",&k); beat[i][j].clear(); for(int kk=0;kk<k;++kk){ scanf("%d%d",&beatp,&beatm); beat[i][j].push_back(MP(beatp,beatm)); } } } dlx.init(sum[n-1]+n); dlx.m1 = sum[n-1], dlx.m2 = n; for(int i=0;i<n;++i){ for(int j=0;j<mode[i];++j){ int row = (i?sum[i-1]:0)+j+1; dlx.link(row,sum[n-1]+i+1);// exact cover dlx.link(row,(i?sum[i-1]:0)+1);// repeat cover if(mode[i]==2) dlx.link(row,(i?sum[i-1]:0)+2);// repeat cover for(int k=0;k<beat[i][j].size();++k){// repeat cover pair<int,int>tmp = beat[i][j][k]; int beatp = tmp.first; int beatm = tmp.second; int col = (beatp?sum[beatp-1]:0)+beatm+1; dlx.link(row,col); } } } dlx.dance(0,0); printf("Case %d: %d\n",++ca,dlx.best); } return 0;}
HDU 3957 Street Fighter（搜索、DLX、重复覆盖+精确覆盖）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。