【HDU】3498 whosyourdaddy

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define MAXN 10000
  5 #define MAXM 60
  6 #define INF 0x7FFFFFFF
  7 using namespace std;
  8 bool G[MAXM][MAXM];
  9 int R[MAXN], L[MAXN], U[MAXN], D[MAXN];
 10 int size, ans, C[MAXN], S[MAXN], H[MAXN];
 11 bool vis[MAXM];
 12 void Init(int n)
 13 {
 14     int i;
 15     memset(G, false, sizeof(G));
 16     for (i = 0; i <= n; i++)
 17     {
 18         R[i] = i + 1;
 19         L[i + 1] = i;
 20         U[i] = D[i] = i;
 21         S[i] = 0;
 22         H[i] = -1;
 23     }
 24     R[n] = 0;
 25     size = n + 1;
 26 }
 27 void Link(int r, int c)
 28 {
 29     U[size] = c;
 30     D[size] = D[c];
 31     U[D[c]] = size;
 32     D[c] = size;
 33     if (H[r] < 0)
 34         H[r] = L[size] = R[size] = size;
 35     else
 36     {
 37         L[size] = H[r];
 38         R[size] = R[H[r]];
 39         L[R[H[r]]] = size;
 40         R[H[r]] = size;
 41     }
 42     S[c]++;
 43     C[size++] = c;
 44 }
 45 void Remove(int c)
 46 {
 47     int i;
 48     for (i = D[c]; i != c; i = D[i])
 49     {
 50         L[R[i]] = L[i];
 51         R[L[i]] = R[i];
 52     }
 53 }
 54 void Resume(int c)
 55 {
 56     int i;
 57     for (i = D[c]; i != c; i = D[i])
 58         L[R[i]] = R[L[i]] = i;
 59 }
 60 int A()
 61 {
 62     int i, j, k, res;
 63     memset(vis, false, sizeof(vis));
 64     for (res = 0, i = R[0]; i; i = R[i])
 65     {
 66         if (!vis[i])
 67         {
 68             res++;
 69             for (j = D[i]; j != i; j = D[j])
 70             {
 71                 for (k = R[j]; k != j; k = R[k])
 72                     vis[C[k]] = true;
 73             }
 74         }
 75     }
 76     return res;
 77 }
 78 void Dance(int now)
 79 {
 80     if (R[0] == 0)
 81         ans = min(ans, now);
 82     else if (now + A() < ans)
 83     {
 84         int i, j, temp, c;
 85         for (temp = INF,i = R[0]; i; i = R[i])
 86         {
 87             if (temp > S[i])
 88             {
 89                 temp = S[i];
 90                 c = i;
 91             }
 92         }
 93         for (i = D[c]; i != c; i = D[i])
 94         {
 95             Remove(i);
 96             for (j = R[i]; j != i; j = R[j])
 97                 Remove(j);
 98             Dance(now + 1);
 99             for (j = L[i]; j != i; j = L[j])
100                 Resume(j);
101             Resume(i);
102         }
103     }
104 }
105 int main()
106 {
107     int n, m, u, v, i, j;
108     while (~scanf("%d%d", &n, &m))
109     {
110         Init(n);
111         while (m--)
112         {
113             scanf("%d%d", &u, &v);
114             G[u][v] = G[v][u] = true;
115         }
116         for (i = 1; i <= n; i++)
117         {
118             G[i][i] = true;
119             for (j = 1; j <= n; j++)
120             {
121                 if (G[i][j])
122                     Link(i, j);
123             }
124         }
125         ans = INF;
126         Dance(0);
127         printf("%d\n", ans);
128     }
129     return 0;
130 }