HDU 3498 whosyourdaddy(DLX重复覆盖)

#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("%d\n",fans);
    }
    return 0;
}