【HDOJ】5046 Airport

DLX简单题目。
  1 /* 5046 */
  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 const int maxn = 65;
 43 int N, K;
 44 __int64 X[maxn], Y[maxn];
 45 __int64 M[maxn][maxn];
 46 
 47 typedef struct {
 48     static const int maxc = 65;
 49     static const int maxr = 65;
 50     static const int maxn = 65*65+5;
 51     
 52     int n, sz;
 53     int S[maxc];
 54     
 55     int col[maxn];
 56     int L[maxn], R[maxn], U[maxn], D[maxn];
 57     
 58     int ansd;
 59     bool visit[maxc];
 60     
 61     void init(int n_) {
 62         n = n_;
 63         
 64         rep(i, 0, n+1) {
 65             L[i] = i - 1;
 66             R[i] = i + 1;
 67             U[i] = i;
 68             D[i] = i;
 69             col[i] = i;
 70         }
 71         L[0] = n;
 72         R[n] = 0;
 73         
 74         sz = n + 1;
 75         memset(S, 0, sizeof(S));
 76     }
 77     
 78     void addRow(vi columns) {
 79         int first = sz;
 80         int size = SZ(columns);
 81         
 82         rep(i, 0, size) {
 83             int c = columns[i];
 84             
 85             L[sz] = sz - 1;
 86             R[sz] = sz + 1;
 87             
 88             D[sz] = c;
 89             U[sz] = U[c];
 90             D[U[c]] = sz;
 91             U[c] = sz;
 92             
 93             col[sz] = c;
 94             
 95             ++S[c];
 96             ++sz;
 97         }
 98         
 99         L[first] = sz - 1;
100         R[sz - 1] = first;
101     }
102     
103     void remove(int c) {
104         for (int i=D[c]; i!=c; i=D[i]) {
105             L[R[i]] = L[i];
106             R[L[i]] = R[i];
107         }
108     }
109     
110     void restore(int c) {
111         for (int i=D[c]; i!=c; i=D[i]) {
112             L[R[i]] = i;
113             R[L[i]] = i;
114         }
115     }
116     
117     int H() {
118         int ret = 0;
119         
120         memset(visit, false, sizeof(visit));
121         
122         for (int c=R[0]; c!=0; c=R[c]) {
123             if (visit[c])
124                 continue;
125             ++ret;
126             visit[c] = true;
127             for (int i=D[c]; i!=c; i=D[i]) {
128                 for (int j=R[i]; j!=i; j=R[j]) {
129                     visit[col[j]] = true;
130                 }
131             }
132         }
133         
134         return ret;
135     }
136     
137     bool dfs(int d) {
138         if (R[0] == 0) {
139             return d<=K;
140         }
141         
142         int delta = H();
143         if (d+delta > K)
144             return false;
145         
146         int c = R[0];
147         for (int i=R[0]; i!=0; i=R[i]) {
148             if (S[i] < S[c])
149                 c = i;
150         }
151         
152         for (int i=D[c]; i!=c; i=D[i]) {
153             remove(i);
154             for (int j=R[i]; j!=i; j=R[j]) {
155                 remove(j);
156             }
157             if( dfs(d + 1) )    return true;
158             for (int j=L[i]; j!=i; j=L[j]) {
159                 restore(j);
160             }
161             restore(i);
162         }
163         
164         return false;
165     }
166     
167 } DLX;
168 
169 DLX solver;
170 
171 __int64 Length(int i, int j) {
172     return abs(X[i]-X[j]) + abs(Y[i]-Y[j]);
173 }
174 
175 bool judge(__int64 d) {
176     solver.init(N);
177     
178     rep(i, 1, N+1) {
179         vi columns;
180         rep(j, 1, N+1) {
181             if (M[i][j] <= d) {
182                 columns.pb(j);
183             }
184         }
185         if (SZ(columns) > 0) {
186             solver.addRow(columns);
187         }
188     }
189     
190     return solver.dfs(0);
191 }
192 
193 void solve() {
194     rep(i, 1, N+1) {
195         M[i][i] = 0;
196         rep(j, 1, i)
197             M[i][j] = M[j][i] = Length(i, j);
198     }
199     
200     __int64 l, r, mid;
201     __int64 ans;
202     
203     l = 0;
204     r = ans = 5e9;
205     while (r >= l) {
206         mid = (r + l)>>1;
207         if (judge(mid)) {
208             ans = mid;
209             r = mid - 1;
210         } else {
211             l = mid + 1;
212         }
213     }
214     
215     printf("%I64d
", ans);
216 }
217 
218 int main() {
219     ios::sync_with_stdio(false);
220     #ifndef ONLINE_JUDGE
221         freopen("data.in", "r", stdin);
222         freopen("data.out", "w", stdout);
223     #endif
224     
225     int t;
226     
227     scanf("%d", &t);
228     rep(tt, 1, t+1) {
229         scanf("%d %d", &N, &K);
230         rep(i, 1, N+1)
231             scanf("%I64d %I64d", &X[i], &Y[i]);
232         printf("Case #%d: ", tt);
233         solve();
234     }
235     
236     #ifndef ONLINE_JUDGE
237         printf("time = %d.
", (int)clock());
238     #endif
239     
240     return 0;
241 }