[HDU3498] whosyourdaddy

 1 #include<bits/stdc++.h>
 2 #define FOR(i,p,X) for(int i=X[p];i!=p;i=X[i])
 3 #define For(i,a,b) for(int i=(a),i_end=(b);i<=i_end;++i)
 4 using namespace std;
 5 const int N=60;
 6 int n,m,ans;
 7 vector<int>G[N];
 8 struct DLX{  
 9     int L[N*N],R[N*N],U[N*N],D[N*N];
10     int C[N*N],H[N],cnt[N],vis[N],id;
11     void init(){  
12         For(i,0,n){  
13             cnt[i]=0;U[i]=D[i]=i;  
14             L[i+1]=i;R[i]=i+1;  
15         }  
16         R[n]=0;id=n+1;  
17         memset(H,-1,sizeof(H));  
18     }  
19     void Link(int r,int c){  
20         cnt[c]++;C[id]=c;  
21         U[id]=U[c];D[U[c]]=id;  
22         D[id]=c;U[c]=id;  
23         if(!~H[r]) H[r]=L[id]=R[id]=id;  
24         else{  
25             L[id]=L[H[r]];R[L[H[r]]]=id;  
26             R[id]=H[r];L[H[r]]=id;  
27         }  
28         id++;  
29     }
30     void Remove(int sz){
31         FOR(j,sz,D)L[R[j]]=L[j],R[L[j]]=R[j];  
32     }  
33     void Resume(int sz){  
34         FOR(j,sz,D)L[R[j]]=R[L[j]]=j;  
35     } 
36     int h(){  
37         int res=0;  
38         memset(vis,0,sizeof(vis));  
39         FOR(i,0,R){
40             if(vis[i])continue;  
41             ++res;  
42             FOR(j,i,D)FOR(k,j,R)
43                 vis[C[k]]=1;
44         }
45         return res;  
46     }  
47     void Dance(int k){  
48         if(k+h()>=ans)return;  
49         int pos=R[0];
50         if(!pos){  
51             if(k<ans)ans=k;  
52             return;  
53         }
54         FOR(i,0,R)if(cnt[pos]>cnt[i])pos=i; 
55         FOR(i,pos,D){
56             Remove(i);
57             FOR(j,i,R)Remove(j);  
58             Dance(k+1);  
59             FOR(j,i,R)Resume(j);  
60             Resume(i);  
61         }
62     }
63 }dlx;
64 int main(){
65     while(scanf("%d%d",&n,&m)!=-1){  
66         dlx.init();
67         For(i,0,n)G[i].clear(),G[i].push_back(i);
68         For(i,1,m){
69             int u,v;
70             scanf("%d%d",&u,&v);  
71             G[u].push_back(v);G[v].push_back(u);  
72         }
73         For(i,1,n)For(j,0,G[i].size()-1)
74             dlx.Link(i,G[i][j]);
75         ans=n;
76         dlx.Dance(0);  
77         printf("%d\n",ans);
78     }
79     return 0;  
80 }