hdu 3498 whosyourdaddy 重复覆盖

重复覆盖的入门题，和精确覆盖不一样，删除的时候只删除一行多列。
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define pb(x) push_back(x)
  4 #define ll long long
  5 #define mk(x, y) make_pair(x, y)
  6 #define lson l, m, rt<<1
  7 #define mem(a) memset(a, 0, sizeof(a))
  8 #define rson m+1, r, rt<<1|1
  9 #define mem1(a) memset(a, -1, sizeof(a))
 10 #define mem2(a) memset(a, 0x3f, sizeof(a))
 11 #define rep(i, a, n) for(int i = a; i<n; i++)
 12 #define ull unsigned long long
 13 typedef pair<int, int> pll;
 14 const double PI = acos(-1.0);
 15 const double eps = 1e-8;
 16 const int mod = 1e9+7;
 17 const int inf = 1061109567;
 18 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
 19 const int maxn = 305;
 20 const int maxNode = 5000;
 21 struct DLX {
 22     int L[maxNode], R[maxNode], U[maxNode], D[maxNode], row[maxNode], col[maxNode];
 23     int S[maxn], H[maxn], deep, ans[maxn], sz, n, m;
 24     void remove(int c) {
 25         for(int i = D[c]; i!=c; i = D[i]) {
 26             L[R[i]] = L[i] ;
 27             R[L[i]] = R[i] ;
 28         }
 29     }
 30     void resume(int c) {
 31         for(int i = U[c]; i!=c; i = U[i]) {
 32             L[R[i]] = i;
 33             R[L[i]] = i;
 34         }
 35     }
 36     int h() {
 37         int cnt = 0;
 38         int vis[105];
 39         mem(vis);
 40         for(int i = R[0]; i!=0; i = R[i]) {
 41             if(!vis[i]) {
 42                 cnt++;
 43                 vis[i] = 1;
 44                 for(int j = D[i]; j!=i; j = D[j]) {
 45                     for(int k = R[j]; k!=j; k = R[k]) {
 46                         vis[col[k]] = 1;
 47                     }
 48                 }
 49             }
 50         }
 51         return cnt;
 52     }
 53     void dfs(int d) {
 54         if(d+h()>=deep)             //剪枝， 如果当前步数加上至少需要的步数大于已有的答案， 就直接return
 55             return ;
 56         if(R[0] == 0) {
 57             deep = min(deep, d);
 58             return ;
 59         }
 60         int c = R[0];
 61         for(int i = R[0]; i!=0; i = R[i])
 62             if(S[c]>S[i])
 63                 c = i;
 64         for(int i = D[c]; i!=c; i = D[i]) {
 65             remove(i);
 66             for(int j = R[i]; j!=i; j = R[j])
 67                 remove(j);
 68             dfs(d+1);
 69             for(int j = L[i]; j!=i; j = L[j])
 70                 resume(j);
 71             resume(i);
 72         }
 73         return ;
 74     }
 75     void add(int r, int c) {
 76         sz++;
 77         row[sz] = r;
 78         col[sz] = c;
 79         S[c]++;
 80         U[sz] = U[c];
 81         D[sz] = c;
 82         D[U[c]] = sz;
 83         U[c] = sz;
 84         if(~H[r]) {
 85             R[sz] = H[r];
 86             L[sz] = L[H[r]];
 87             L[R[sz]] = sz;
 88             R[L[sz]] = sz;
 89         } else {
 90             H[r] = L[sz] = R[sz] = sz;
 91         }
 92     }
 93     void init(){
 94         mem1(H);
 95         deep = inf;
 96         for(int i = 0; i<=n; i++) {
 97             R[i] = i+1;
 98             L[i] = i-1;
 99             U[i] = i;
100             D[i] = i;
101         }
102         mem(S);
103         R[n] = 0;
104         L[0] = n;
105         sz = n;
106     }
107     void solve() {
108         init();
109         int a, b, g[60][60];
110         mem(g);
111         while(m--) {
112             scanf("%d%d", &a, &b);
113             g[a][b] = g[b][a] = 1;
114         }
115         for(int i = 1; i<=n; i++) {
116             for(int j = 1; j<=n; j++) {
117                 if(g[i][j]|| i==j)
118                     add(i, j);
119             }
120         }
121         dfs(0);
122         printf("%d
", deep);
123     }
124 }dlx;
125 int main()
126 {
127     int n, m;
128     while(~scanf("%d%d", &dlx.n, &dlx.m)) {
129         dlx.solve();
130     }
131     return 0;
132 }