很久以前就看到的一个经典题，一直没做，今天拿来练手。街霸
给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
",++ca,dlx.best);
}
return 0;
}