【HDOJ】3957 Street Fighter

一定要注意审题啊，题目说的是选出做少的英雄打败其余处在任何模式下的英雄。
共有Sigma(num of model)个方案，每个方案有Sigma(num of model)+n个决策。
挺不错的一道精确覆盖的题目，最近发现精确覆盖很有意思。
  1 /* 3957 */
  2 #include <iostream>
  3 #include <string>
  4 #include <map>
  5 #include <queue>
  6 #include <set>
  7 #include <stack>
  8 #include <vector>
  9 #include <deque>
 10 #include <algorithm>
 11 #include <cstdio>
 12 #include <cmath>
 13 #include <ctime>
 14 #include <cstring>
 15 #include <climits>
 16 #include <cctype>
 17 #include <cassert>
 18 #include <functional>
 19 #include <iterator>
 20 #include <iomanip>
 21 using namespace std;
 22 //#pragma comment(linker,"/STACK:102400000,1024000")
 23 
 24 #define sti                set<int>
 25 #define stpii            set<pair<int, int> >
 26 #define mpii            map<int,int>
 27 #define vi                vector<int>
 28 #define pii                pair<int,int>
 29 #define vpii            vector<pair<int,int> >
 30 #define rep(i, a, n)     for (int i=a;i<n;++i)
 31 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 32 #define clr                clear
 33 #define pb                 push_back
 34 #define mp                 make_pair
 35 #define fir                first
 36 #define sec                second
 37 #define all(x)             (x).begin(),(x).end()
 38 #define SZ(x)             ((int)(x).size())
 39 #define lson            l, mid, rt<<1
 40 #define rson            mid+1, r, rt<<1|1
 41 
 42 typedef struct {
 43     static const int maxc = 30*3+5;
 44     static const int maxr = 60;
 45     static const int maxn = 60*60+5;
 46     
 47     int nmodel;
 48     int n, sz;
 49     int S[maxc];
 50     
 51     int col[maxn];
 52     int L[maxn], R[maxn], U[maxn], D[maxn];
 53     bool visit[maxc];
 54     
 55     int ansd;
 56     
 57     void init(int nmodel_, int n_) {
 58         ansd = INT_MAX;
 59         n = n_;
 60         nmodel = nmodel_;
 61         
 62         rep(i, 0, n+1) {
 63             L[i] = i - 1;
 64             R[i] = i + 1;
 65             U[i] = i;
 66             D[i] = i;
 67             col[i] = i;
 68         }
 69         L[0] = n;
 70         R[n] = 0;
 71         
 72         sz = n + 1;
 73         memset(S, 0, sizeof(S));
 74     }
 75     
 76     void addRow(vi columns) {
 77         int first = sz;
 78         int size = SZ(columns);
 79         
 80         rep(i, 0, size) {
 81             int c = columns[i];
 82             
 83             L[sz] = sz - 1;
 84             R[sz] = sz + 1;
 85             
 86             D[sz] = c;
 87             U[sz] = U[c];
 88             D[U[c]] = sz;
 89             U[c] = sz;
 90             
 91             col[sz] = c;
 92             
 93             ++S[c];
 94             ++sz;
 95         }
 96         
 97         L[first] = sz - 1;
 98         R[sz - 1] = first;
 99     }
100     
101     void remove(int c) {
102         L[R[c]] = L[c];
103         R[L[c]] = R[c];
104         for (int i=D[c]; i!=c; i=D[i]) {
105             for (int j=R[i]; j!=i; j=R[j]) {
106                 U[D[j]] = U[j];
107                 D[U[j]] = D[j];
108                 --S[col[j]];
109             }
110         }
111     }
112     
113     void restore(int c) {
114         L[R[c]] = c;
115         R[L[c]] = c;
116         for (int i=D[c]; i!=c; i=D[i]) {
117             for (int j=R[i]; j!=i; j=R[j]) {
118                 U[D[j]] = j;
119                 D[U[j]] = j;
120                 ++S[col[j]];
121             }
122         }
123     }
124     
125     void remove_col(int c) {
126         for (int i=D[c]; i!=c; i=D[i]) {
127             L[R[i]] = L[i];
128             R[L[i]] = R[i];
129         }
130     }
131     
132     void restore_col(int c) {
133         for (int i=D[c]; i!=c; i=D[i]) {
134             L[R[i]] = i;
135             R[L[i]] = i;
136         }
137     }
138     
139     int H() {
140         // return 0;
141         int ret = 0;
142         
143         memset(visit, false, sizeof(visit));
144         for (int c=R[0]; c!=0&&c<=nmodel; c=R[c]) {
145             if (visit[c])
146                 continue;
147             ++ret;
148             visit[c] = true;
149             for (int i=D[c]; i!=c; i=D[i]) {
150                 for (int j=R[i]; j!=i; j=R[j])
151                     visit[col[j]] = true;
152             }
153         }
154         
155         return ret;
156     }
157     
158     void dfs(int d) {
159         if (R[0]==0 || R[0]>nmodel) {
160             ansd = min(ansd, d);
161             return ;
162         }
163         
164         int delta = H();
165         
166         if (d+delta >= ansd)
167             return ;
168         
169         int c = R[0];
170         for (int i=R[0]; i!=0&&i<=nmodel; i=R[i]) {
171             if (S[i] < S[c])
172                 c = i;
173         }
174         
175         for (int i=D[c]; i!=c; i=D[i]) {
176             remove_col(i);
177             for (int j=R[i]; j!=i; j=R[j]) {
178                 if (col[j] <= nmodel)
179                     remove_col(j);
180             }
181             for (int j=R[i]; j!=i; j=R[j]) {
182                 if (col[j] > nmodel)
183                     remove(col[j]);
184             }
185             dfs(d + 1);
186             for (int j=L[i]; j!=i; j=L[j]) {
187                 if (col[j] > nmodel)
188                     restore(col[j]);
189             }
190             for (int j=L[i]; j!=i; j=L[j]) {
191                 if (col[j] <= nmodel)
192                     restore_col(j);
193             }
194             restore_col(i);
195         }
196     }
197     
198     void solve() {
199         ansd = INT_MAX;
200         dfs(0);
201     }
202     
203 } DLX;
204 
205 typedef struct {
206     int m, k[2];
207     pii p[2][11];
208 } hero_t;
209 
210 DLX solver;
211 int ID[30][2];
212 int nmodel, n;
213 hero_t hero[30];
214 
215 void solve() {
216     solver.init(nmodel, n+nmodel);
217     
218     rep(i, 0, n) {
219         rep(j, 0, hero[i].m) {
220             // each model has a plan
221             vi columns;
222             // cover i-th hero
223             columns.pb(nmodel+i+1);    
224             // cover 0-th plan
225             columns.pb(ID[i][0]);
226             // may cover 1-th plan
227             if (hero[i].m == 2)
228                 columns.pb(ID[i][1]);
229             rep(k, 0, hero[i].k[j]) {
230                 int role_id = hero[i].p[j][k].fir;
231                 int model_id = hero[i].p[j][k].sec;
232                 columns.pb(ID[role_id][model_id]);
233             }
234             
235             solver.addRow(columns);
236         }
237     }
238     
239     solver.solve();
240     
241     printf("%d
", solver.ansd);
242 }
243 
244 int main() {
245     ios::sync_with_stdio(false);
246     #ifndef ONLINE_JUDGE
247         freopen("data.in", "r", stdin);
248         freopen("data.out", "w", stdout);
249     #endif
250     
251     int t;
252     
253     scanf("%d", &t);
254     rep(tt, 1, t+1) {
255         scanf("%d", &n);
256         nmodel = 0;
257         rep(i, 0, n) {
258             scanf("%d", &hero[i].m);
259             rep(j, 0, hero[i].m) {
260                 scanf("%d", &hero[i].k[j]);
261                 rep(k, 0, hero[i].k[j])
262                     scanf("%d %d", &hero[i].p[j][k].fir, &hero[i].p[j][k].sec);
263                 ID[i][j] = ++nmodel;
264             }
265         }
266         printf("Case %d: ", tt);
267         solve();
268     }
269     
270     #ifndef ONLINE_JUDGE
271         printf("time = %d.
", (int)clock());
272     #endif
273     
274     return 0;
275 }