本文共 3991 字，大约阅读时间需要 13 分钟。
DLX简单题目。
1 /* 5046 */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 using namespace std; 22 //#pragma comment(linker,"/STACK:102400000,1024000") 23 24 #define sti set 25 #define stpii set > 26 #define mpii map 27 #define vi vector 28 #define pii pair 29 #define vpii vector > 30 #define rep(i, a, n) for (int i=a;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\n", ans);216 }217 218 int main() {219 ios::sync_with_stdio(false);220 #ifndef ONLINE_JUDGE221 freopen("data.in", "r", stdin);222 freopen("data.out", "w", stdout);223 #endif224 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_JUDGE237 printf("time = %d.\n", (int)clock());238 #endif239 240 return 0;241 }
转载于:https://www.cnblogs.com/bombe1013/p/4980152.html