//acm.hdu.edu.cn/showproblem.php?pid=3498
n个点，m条无向边，删除一个点会把与其相邻的点一起删掉，问最少删几次可以删掉所有点。
DLX可重复覆盖模板...
AC代码：
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
const int maxn=60;
int L[maxn*maxn],R[maxn*maxn],U[maxn*maxn],D[maxn*maxn];
int C[maxn*maxn],H[maxn],cnt[maxn],vis[maxn];
int n,m,id,fans;
vector<int> G[maxn];
void init(){
for(int i=0;i<=n;i ){
G[i].clear();
G[i].push_back(i);
cnt[i] = 0; U[i] = D[i] = i;
L[i 1] = i; R[i] = i 1;
}
R[n] = 0; id = n 1;
memset(H,-1,sizeof(H));
}
void Link(int r, int c){
cnt[c] ; C[id] = c;
U[id] = U[c]; D[ U[c] ] = id;
D[id] = c; U[c] = id;
if(H[r] == -1) H[r] = L[id] = R[id] = id;
else{
L[id] = L[ H[r] ]; R[ L[ H[r] ] ] = id;
R[id] = H[r]; L[ H[r] ] = id;
}
id ;
}
void Remove(int Size){
for(int j=D[Size];j!=Size;j=D[j])
L[ R[j] ] = L[j], R[ L[j] ] = R[j];
}
void Resume(int Size){
for(int j=D[Size];j!=Size;j=D[j])
L[ R[j] ] = R[ L[j] ] = j;
}
int h(){
int sum = 0;
memset(vis, 0, sizeof(vis));
for(int i=R[0];i;i=R[i]){
if(vis[i]) continue;
sum ;
for(int j=D[i];j!=i;j=D[j]){
for(int k=R[j];k!=j;k=R[k])
vis[ C[k] ] = 1;
}
}
return sum;
}
void DLX(int k){
int mm = maxn, pos;
if(k h() >= fans) return;
if( !R[0] ){
if(k < fans) fans = k;
return ;
}
for(int i=R[0];i;i=R[i])
if(mm > cnt[i]) mm = cnt[i] , pos = i;
for(int i=D[pos];i!=pos;i=D[i]){
Remove(i);
for(int j=R[i];j!=i;j=R[j]) Remove(j);
DLX(k 1);
for(int j=R[i];j!=i;j=R[j]) Resume(j);
Resume(i);
}
}
int main(){
int u,v;
while(scanf("%d%d",&n,&m) != -1){
init();
for(int i=0;i<m;i ){
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;i ){
for(unsigned int j=0;j<G[i].size();j ){
int t=G[i][j];
Link(i,t);
}
}
fans=n;
DLX(0);
printf("%dn",fans);
}
return 0;
}
