DancingLinks刷題集

?HDU 3663?Power Stations 精確覆蓋?

題意：每個城市i有xi->yi天可以成為發射站，發射站覆蓋范圍為與該站有一條邊鏈接的城市。

同時，每個每天城市必須且只能被一個發射站覆蓋

天數D<=5。每個城市的發射站關閉后就不再開啟。即只能選擇一段區間。

問若能做到，則輸出每個城市開啟時間與關閉時間

否則輸出No solution

做法：

1.天數城市可獨立看待，故每個城市每天看做一列。

2.在此區間內取一段子區間，注意到D很小，可枚舉起點時刻終點時刻，每個城市每個方案作為一行。

3.對每個方案可覆蓋到的城市及各天，則對該行該列設1

4.為解決每個城市只能取一段區間，則對每個城市設置一個新的列，該城市所有方案在該列設1，使不重復選擇。

5.注意設置每個城市發射站未開啟的方案行。因為不開是可行的。6。

注意多輸出一行空行

//2014.11.7

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;#define N 1004
#define M 850
#define T 820000
#define INF 0x3f3f3f3f
vector<int>vec[66];
int dir[10];
bool g[66][66];
vector<int>v;
struct Day{int x,y;Day(){};Day(int xx, int yy): x(xx), y(yy){};
}p[66], ans[66], rec[N];
int yingying, f[N];
void dabiao(){int i;dir[0] = 0;for(i = 1; i <= 5; i++) dir[i] = i + dir[i-1];
}
struct DLX{int L[T], R[T], U[T], D[T];int head[N];int cnt[M], col[T], row[T], id, n, m;void init(int nn, int mm){this->n = nn;this->m = mm;int i;for(i = 0; i <= m; i++){D[i] = U[i] = i;L[i] = i-1;    R[i] = i + 1;}id = m + 1;R[m] = 0;    L[0] = m;memset(cnt, 0, sizeof(cnt));memset(head, -1, sizeof(head));}void add(int r, int c){D[id] =  c;    U[id] = U[c];D[U[c]] = id;    U[c]  = id;if(head[r] < 0 ){head[r] = L[id] = R[id] = id;}else {L[id] = head[r];    R[id] = R[head[r]];L[R[head[r]]] =id;    R[head[r]] = id;head[r] = id;}cnt[c] ++;    col[id] = c;    row[id] =r;id ++;}void del(int x){int i, j;L[R[x]] = L[x];    R[L[x]] = R[x];for(i = D[x]; i != x; i = D[i]){for(j = R[i]; j != i; j = R[j]){cnt[col[j]] --;U[D[j]] = U[j];    D[U[j]] = D[j];}}}void resume(int x){int i, j;for(i = U[x]; i != x; i = U[i]){for(j = L[i]; j != i; j = L[j]){cnt[col[j]] ++;D[U[j]] = j;    U[D[j]] = j;}}L[R[x]] = x;    R[L[x]] = x;}bool dfs(){if(R[0] == 0) return true;int idx , temp, i, j;temp = INF;for(i = R[0]; i != 0; i = R[i]){if(cnt[i] < temp){temp = cnt[i];idx = i;}}if(temp == 0) return false;del(idx);for(i = D[idx]; i != idx; i = D[i]){Day tttt = ans[f[row[i]]];ans[f[row[i]]] = rec[row[i]];for(j = R[i]; j != i; j = R[j]){del(col[j]);}if(dfs()) return true;for(j = L[i]; j != i; j = L[j]){resume(col[j]);}ans[f[row[i]]] = tttt;}resume(idx);return false;}
}dlx;bool gao(int n, int d){int sum = 0, i, j, k, t, tt;for(i = 1; i <= n; i++){sum += dir[p[i].y - p[i].x];}dlx.init(sum, n * d + n);sum = 0;for(i = 1; i <= n; i++){for(j = p[i].x; j <= p[i].y; j++){for(k = j; k <= p[i].y; k++){++sum;for(tt = 0; tt < vec[i].size(); tt++){for(t = j; t <= k; t++){dlx.add(sum, (vec[i][tt]-1)*d+t);}}dlx.add(sum, n * d +i);rec[sum] = Day(j, k);f[sum] = i;}}}for(i = 1; i <= n; i ++){dlx.add(++sum, n * d + i);f[sum] = n + 1;}return dlx.dfs();}int main(void){int n, m, d, i, j, x, y;dabiao();while(scanf("%d%d%d", &n, &m, &d) != EOF){fill(vec, vec+66, vector<int>() );memset(g, false, sizeof(g));while(m--){scanf("%d%d", &x, &y);if(g[x][y]) continue;g[x][y] = g[y][x] = true;vec[x].push_back(y);    vec[y].push_back(x);}for(i = 1; i <= n; i++){scanf("%d%d", &p[i].x, &p[i].y);vec[i].push_back(i);ans[i] = Day(0, 0);}yingying = n;if(gao(n, d)){for(i = 1; i <= n; i++){printf("%d %d\n", ans[i].x, ans[i].y);}}else printf("No solution\n");printf("\n");}return 0;
}

View Code

HDU 2828 Lamp

重復覆蓋+判斷沖突?

題意：有N盞燈可以由M個開關控制，對于第i盞燈，當條件A|| B || C。。。滿足則燈亮，條件X為j開關OFF或ON狀態。

問開關處于何種狀態時，燈是全開的。SPJ

做法：

建圖的第一部分很簡單，以N盞燈為列，每個開關的開/關狀態各為一行，對處于此狀態為亮的燈為1.

然后是開關的狀態只能取一個的解決方法。對于每個開關狀態on / off是否采用，設置vis數組，若dfs時對應的另一個狀態已經采用，則此狀態非法，不搜。

以上，可解決。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;#define N 1004
#define T 1000004
#define INF 0x3f3f3f3fint f[N][N>>1], ans[504];
vector<int>v;
int M ;
struct DLX{int r[T], l[T], u[T], d[T];int cnt[N], col[T], row[N], head[N];bool vis[N];int n, id;void init(int n){this->n = n;int i;for(i = 0; i <= n; i++){d[i] = u[i] = i;l[i] = i - 1;    r[i] = i + 1;}id = n + 1;r[n] = 0;    l[0] = n;memset(cnt, 0, sizeof(cnt));memset(vis, false, sizeof(vis));memset(head, -1, sizeof(head));}void add(int R, int C){d[id] =  C;    u[id] = u[C];    d[u[C]] = id;    u[C]  = id;if(head[R] < 0 ){head[R] = l[id] = r[id] = id;}else {l[id] = head[R];    r[id] = r[head[R]];l[r[head[R]]] =id;    r[head[R]] = id;head[R] = id;}cnt[C] ++;    col[id] = C;    row[id] =R;id ++;}void remove(int x){int i;for(i = u[x]; i != x; i = u[i]){l[r[i]] = l[i];r[l[i]] = r[i];}}void resume(int x){int i;for(i = d[x]; i != x; i = d[i]){l[r[i]] = i;    r[l[i]] = i;}}bool dfs(){if(r[0] == 0) return true;int i, c = r[0], j;for(i = r[0]; i != 0; i = r[i]){if(cnt[i] <cnt[c]) c = i;}for(i = d[c]; i != c; i = d[i]){if(vis[row[i]^1] ) continue;vis[row[i]] = true;remove(i);for(j = r[i]; j != i; j = r[j]){remove(j);}if(dfs()) return true;for(j = l[i]; j != i; j = l[j])                    resume(j);resume(j);resume(i);        vis[row[i]] = false;}return false;}}dlx;bool gao(int n, int m){dlx.init(n);m <<= 1;int i, j;for(i = 0; i < m; i++){for(j = 1; j <= n; j++){if(f[i][j]){dlx.add(i, j);}}}return dlx.dfs();
}int main(){int n, m, i, k, x;char op[10];while(scanf("%d%d", &n, &m) != EOF){memset(f, 0, sizeof(f));M = n;    for(i = 1; i <= n; i++){scanf("%d", &k);while(k--){scanf("%d%s", &x, op);x--;if(op[1] == 'N'){f[x<<1][i] = 1; }else f[x<<1|1][i] = 1;}}if(gao(n, m)){for(i = 0; i < m; i++){printf("%s%c", dlx.vis[i<<1] ? "ON": "OFF", i == m - 1? '\n' : ' ');}}else printf("-1\n");}return 0;
}

View Code

zoj 3209?Treasure Map

題意：在?n*m的平面中有p?(1 <=?n,?m?<= 30, 1 <=?p?<= 500)個小矩形，每個小矩形有其所在位置，問從中選出最少數目個使得覆蓋整個平面并且不重合。

直接暴力碾壓過去。。對每個小矩形為行，為其能覆蓋的點（格子？）為列，跑DLX

注意每個點應該[x0,x1), [y0, y1) 即統一只覆蓋某邊界

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;#define N 505
#define M 1005
#define T 500005
#define INF 0x3f3f3f3f
struct DLX{int r[T], u[T], l[T], d[T];int cnt[M], col[T], head[N];int n, id;void init(int nt){this->n = nt;int i;for(i = 0; i <= n; i++){d[i] = u[i] = i;l[i] = i - 1;    r[i] = i + 1;}id = n + 1;r[n] = 0;    l[0] = n;memset(cnt, 0, sizeof(cnt));memset(head, -1, sizeof(head));}void add(int rr, int cc){d[id] = cc;    u[id] = u[cc];d[u[cc]] = id;    u[cc] = id;if(head[rr] < 0){head[rr] = l[id] = r[id] = id;}else {l[id] = head[rr];    r[id] = r[head[rr]];l[r[head[rr]]] = id;    r[head[rr]] = id;head[rr] = id;}cnt[cc] ++;    col[id] = cc;id ++;}void remove(int x){int i, j;l[r[x]] = l[x];    r[l[x]] = r[x];for(i = d[x]; i != x; i = d[i]){for(j = r[i]; j != i; j = r[j]){cnt[col[j]] --;    u[d[j]] = u[j];    d[u[j]] = d[j];}}return ;}void resume(int x){int i, j;for(i = u[x]; i != x; i = u[i]){for(j = l[i]; j != i; j = l[j]){cnt[col[j]] ++;d[u[j]] = j;    u[d[j]] = j;}}l[r[x]] = x;    r[l[x]] = x;}int dfs(){if(r[0] == 0) {return 0;}int idx, temp = INF, ans = INF, i, j;for(i = r[0]; i != 0; i = r[i]){if(cnt[i] < temp){temp = cnt[i];idx = i;}}    //    printf("%d\n", idx);if(temp == 0) return INF;remove(idx);for(i = d[idx]; i != idx; i = d[i]){for(j = r[i]; j != i; j = r[j]){remove(col[j]);}ans = min(ans, dfs());for(j = l[i]; j != i; j = l[j]){resume(col[j]);}}resume(idx);return ans + 1;}}dlx;int main(void){int TC, n, p, m, i, j, k, ans;int x1, y1, x2, y2;scanf("%d", &TC);while(TC--){scanf("%d%d%d", &n, &m, &p);dlx.init(m*n);for(i = 1; i <= p; i++){scanf("%d%d%d%d", &x1, &y1, &x2, &y2);for(j = x1; j < x2; j++){for(k = y1; k < y2; k++){dlx.add(i, 1 + j * m + k);}}}ans = dlx.dfs();if(ans >= INF) ans = -1;printf("%d\n", ans);}return 0;
}

View Code

HDU 3498?whosyourdaddy

題意：攻擊一個點可以同時攻擊其相鄰點，（不超過4個），問最少攻擊多少個點能攻擊完所有點。

做法。。裸。。。注意剪枝

if(ct + H() > ANS) return; 是過不了的。。
要if(ct + H() >= ANS) return;才行

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;#define N 60
#define T 4000
#define INF 0x3f3f3f3fbool f[N][N];
int ANS;
struct DLX{int l[T], r[T], u[T], d[T];int cnt[N], head[N], row[T], col[T];bool vis[N];int id, n;void init(int nt){this->n = nt;int i;for(i = 0; i <= n; i++){d[i] = u[i] = i;l[i] = i - 1;    r[i] = i + 1;}id = n + 1;r[n] = 0;    l[0] = n;memset(cnt, 0, sizeof(cnt));memset(head, -1, sizeof(head));}void add(int R, int C){d[id] =  C;    u[id] = u[C];    d[u[C]] = id;    u[C]  = id;if(head[R] < 0 ){head[R] = l[id] = r[id] = id;}else {l[id] = head[R];    r[id] = r[head[R]];l[r[head[R]]] =id;    r[head[R]] = id;head[R] = id;}cnt[C] ++;    col[id] = C;    row[id] =R;id ++;}void remove(int x){int i, j;for(i = u[x]; i != x; i = u[i]){l[r[i]] = l[i];    r[l[i]] = r[i];}}int H(){memset(vis, false, sizeof(vis));int ans = 0, i, j, k;for(i = r[0]; i != 0; i = r[i]){if(vis[i]) continue;ans ++;    vis[i] = true;for(j = d[i]; j != i; j = d[j]){for(k = r[j]; k != j; k = r[k]){vis[col[k]] = true;}}}return ans;}void resume(int x){int i;for(i = d[x]; i != x; i = d[i]){l[r[i]] = i;    r[l[i]] = i;}}void dfs(int ct){if(ct + H() >= ANS) return;if(r[0] == 0) {ANS = min(ANS, ct);return;//    return true;
        }int idx, temp = INF, ans = INF, i, j;for(i = r[0] ;i != 0; i = r[i]){if(cnt[i] < temp){temp = cnt[i];idx = i;}}//    printf("%d\n", idx);for(i = d[idx]; i != idx; i =d[i]){remove(i);for(j = r[i]; j != i; j = r[j]){remove(j);}//if(dfs(ct+1))     ans = true;dfs(ct + 1);for(j = l[i]; j != i; j = l[j]){resume(j);}resume(i);}//    return false;
    }
}dlx;int main(){int n, m, x, y;int i, j;while(scanf("%d%d", &n, &m) != EOF){dlx.init(n);memset(f, false, sizeof(f));while(m--){scanf("%d%d", &x, &y);f[x][y] = f[y][x] = true;}for(i = 1; i <= n; i++){f[i][i] = true;for(j = 1; j <= n; j++){if(f[i][j]) dlx.add(i, j);}}ANS = n;dlx.dfs(0);printf("%d\n", ANS);}return 0;
}

View Code

HDU 3529?Bomberman - Just Search!

題意：炸彈人游戲，在空地放炸彈可以炸到以它為十字中心的最近的磚塊，如果路上有石頭沖擊波就被攔住了。現在設所有炸彈同時爆炸，問最少放多少個炸彈。

做法：繼續裸題。。就是為了練敲板正確度

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;#define N 240
#define M 44
#define T 11560
#define INF 0x3f3f3f3fint ans, mapa[22][22], mapb[22][22];
char map[22][22];
bool f[N][M];
/*
struct DLX{int l[T], r[T], u[T], d[T];int head[N], row[T], col[T], cnt[M];bool vis[M];int id, n;}dlx;
*/struct DLX{int l[T], r[T], u[T], d[T];int cnt[N], head[N], row[T], col[T];bool vis[N];int id, n;void init(int nt){this->n = nt;int i;for(i = 0; i <= n; i++){d[i] = u[i] = i;l[i] = i - 1;    r[i] = i + 1;}id = n + 1;r[n] = 0;    l[0] = n;memset(cnt, 0, sizeof(cnt));memset(head, -1, sizeof(head));}    void add(int rr, int cc){d[id] = cc;    u[id] = u[cc];d[u[cc]] = id;    u[cc] = id;if(head[rr] < 0){head[rr] = l[id] = r[id ] = id;}else{l[id] = head[rr];    r[id] = r[head[rr]];l[r[head[rr]]] = id;    r[head[rr]] = id;head[rr] = id;}col[id] = cc;    row[id] = rr;cnt[cc] ++;id ++;}void del(int x){int i;for(i = u[x]; i != x; i = u[i]) {l[r[i]] = l[i];    r[l[i]] = r[i];}}int H(){memset(vis, false, sizeof(vis));int i, j, k, ans = 0;for(i = r[0]; i != 0; i =r[i]){if(vis[i]) continue;ans ++;    vis[i] = true;for(j = d[i]; j != i; j = d[j]){for(k = r[j] ;k != j; k = r[k]){vis[col[k]] = true;}}}return ans;}void resume(int x){int i;for(i =d[x]; i != x; i =d[i]){l[r[i]] = i;    r[l[i]] = i;}}void dfs(int ct){if(ct + H() >= ans) return;if(r[0] == 0){ans = min(ans, ct);return;}int i, idx, temp = INF, j;for(i = r[0]; i != 0; i = r[i]){if(cnt[i] < temp){temp = cnt[i];idx = i;}}for(i = d[idx]; i != idx; i =d[i]){del(i);for(j = r[i]; j != i; j =r[j]){del(j);}dfs(ct + 1);for(j  = l[i]; j != i; j = l[j]){resume(j);}resume(i);}}}dlx;
int gox[4] = {0, 0, -1, 1}, goy[4] = {-1, 1, 0, 0};int main(){int n, m, i, j, ida, idb;int k, xx, yy;while(scanf("%d%d", &n, &m) != EOF){ida = idb = 0;for(i = 1; i <= n; i++){scanf("%s", map[i]+1);for(j = 1; j <= m; j++){if(map[i][j] == '.') mapa[i][j] = ++ida;else if(map[i][j] == '#') mapb[i][j] = ++idb;}}dlx.init(idb);memset(f, 0, sizeof(f));for(i = 2; i < n; i++){for(j = 2; j < m; j++){if(map[i][j] == '.'){ //void build(int x, int y){for(k = 0; k < 4; k++){xx = i + gox[k];    yy = j + goy[k];while(true){if(map[xx][yy] == '*') break;if(map[xx][yy] == '#'){f[mapa[i][j]][mapb[xx][yy]] = true;break;}xx += gox[k];    yy += goy[k];}}}}}for(i = 1; i <= ida; i++){for(j = 1; j <= idb; j++){if(f[i][j]) dlx.add(i, j);}}//printf("!!\n");ans = ida;dlx.dfs(0);printf("%d\n", ans);}return 0;
}

View Code

HDU 2295?Radar

題意：對于一個發射站可以覆蓋以他為圓心的半徑是 r的園內的城市，每個發射站半徑相同，問使得從備選的M個發射站中選出K個覆蓋所有N個城市的最小半徑是多少。

二分半徑，重復覆蓋，搜索時當ct+H() > K 就是不行

1. 1 ≤ T ≤ 20?
2. 1 ≤ N, M ≤ 50?
3. 1 ≤ K ≤ M?
4. 0 ≤ X, Y ≤ 1000?

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;#define N 55
#define T 3003
#define INF 0x3f3f3f3f
int dis[N][N];
int K;
struct DLX{int l[T], r[T], u[T], d[T];int cnt[N], col[T], row[T], head[N];bool vis[N];int n, id;void init(int nt){int i;this->n = nt;for(i = 0; i <= n; i++){u[i] = d[i] = i;l[i] = i -1;    r[i] = i + 1;}l[0] = n;    r[n] = 0;id = n + 1;memset(cnt, 0, sizeof(cnt));memset(head, -1, sizeof(head));}void add(int x, int y){u[id] = u[y];    d[id] = y;d[u[y]] = id;    u[y] = id;if(head[x] == -1){head[x] = l[id] = r[id] = id;}else{l[id] = head[x];    r[id] = r[head[x]];l[r[head[x]]] = id;    r[head[x]] = id;    }col[id] = y;    row[id] = x;cnt[y] ++;    id++;}void del(int x){int i;for(i = u[x]; i != x; i = u[i]){l[r[i]] = l[i];    r[l[i]] = r[i];}}void resume(int x){int i;for(i = d[x]; i != x; i = d[i]){l[r[i]] = r[l[i]] = i;}}int H(){memset(vis, false, sizeof(vis));int i, j,k, ans = 0;for(i = r[0]; i != 0; i = r[i]){if(vis[i]) continue;ans ++;    vis[i] = true;for(j = d[i]; j != i; j = d[j]){for(k = r[j]; k != j; k = r[k]){vis[col[k]] = true;}}}return ans;}bool dfs(int ct){if(ct + H() > K) return false;if(r[0] == 0) return true;int i, j, idx, temp = INF;for(i = r[0]; i != 0; i = r[i]){if(cnt[i] < temp){temp = cnt[i];    idx = i;}}for(i = d[idx]; i != idx; i = d[i]){del(i);for(j = r[i]; j != i; j =r[j]){del(j);}if(dfs(ct + 1)) return true;for(j = l[i]; j != i; j = l[j]){resume(j);}resume(i);}return false;}}dlx;
int n, m;
struct point{int x, y;
}p[N], q[N];void cal(void ){int i, j;for(i = 1; i <= m; i++)for(j = 1; j <= n; j++)dis[i][j] = (q[i].x-p[j].x)* (q[i].x-p[j].x)+ (q[i].y-p[j].y)* (q[i].y-p[j].y);
}void build(int mid){dlx.init(n);int i, j;for(i = 1; i <= m; i++){for(j = 1; j <= n; j++){if(mid >= dis[i][j]){dlx.add(i, j);}}}}int main(){int TC;scanf("%d", &TC);int i, j;while(TC--){scanf("%d%d%d", &n, &m, &K);for(i = 1;  i <= n; i++){scanf("%d%d", &p[i].x, &p[i].y);}for(j = 1; j <= m; j++){scanf("%d%d", &q[j].x, &q[j].y);}cal();int low = 0, high =INF, mid, ans;while(low <= high){mid = (low + high) >> 1;build(mid);if(dlx.dfs(0)){ans = mid;high = mid - 1;}else low = mid + 1;}printf("%.6f\n", (double)sqrt((double)ans));}return 0;
}

View Code

HDU 3656?Fire station

題意類似，從N個城市中選M個建消防站，使得所有城市到離他最近的消防站的距離最小。

不過直接對一大波范圍二分會T,注意到半徑一定是離消防站某個城市的距離，處理出城市兩兩之間所有距離，二分+重復覆蓋

s (1 ≤ M ≤N ≤ 50), ?(0 ≤ Xi, Yi ≤ 10000)

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;#define N 55
#define T 4003
#define INF 0x3f3f3f3f
int n, m;
int dis[N][N], num[T];
int maxn;
struct DLX{int l[T], r[T], u[T], d[T];int cnt[N], col[T], head[N];bool vis[N];int id, n;void init(int nt){this->n = nt;int i;for(i = 0; i <= n; i++){u[i] = d[i]  = i;l[i] = i-1;    r[i] = i + 1;}l[0] = n;    r[n]  = 0;memset(cnt, 0, sizeof(cnt));memset(head, -1, sizeof(head));id = n + 1;}void add(int x, int y){d[id] = y;    u[id] = u[y];d[u[y]] = id;    u[y] = id;if(head[x] == -1){head[x] = l[id] = r[id] = id;}else{l[id ] = head[x];    r[id] = r[head[x]];l[r[head[x]]] = id;    r[head[x]] = id;head[x] = id;}col[id] = y;    cnt[y] ++;id ++;}void del(int x){int i;for(i = u[x]; i != x; i = u[i]){l[r[i]] = l[i];    r[l[i]] = r[i];}}void resume(int x){int i;for(i = d[x]; i != x; i = d[i]){l[r[i]] = r[l[i]] = i;}}int H(){int i, j, k, ans = 0;memset(vis, false, sizeof(vis));for(i = r[0]; i != 0; i = r[i]){if(vis[i]) continue;ans ++;    vis[i] = true;for(j = d[i]; j != i; j = d[j]){for(k = r[j] ; k != j; k = r[k]){vis[col[k]] = true;}}}return ans;}bool dfs(int ct){if(ct + H() > m) return false;if(r[0 ] == 0) return true;int i, j, idx, temp = INF;for(i = r[0]; i != 0; i = r[i]){if(cnt[i] < temp){temp = cnt[i];idx = i;}}for(i = d[idx]; i != idx; i = d[i]){del(i);for(j = r[i]; j != i; j =r[j]){del(j);}if(dfs(ct + 1)) return true;for(j = l[i]; j != i; j = l[j]){resume(j);}resume(i);}return false;}}dlx;
struct point{int x, y;
}p[N];void cal(){int i, j;dis[0][0] = 0;for(i = 1; i <= n; i++){for(j = 1; j <= n; j++){dis[i][j] = (p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y);//    dis[0][0] = max(dis[0][0], dis[i][j]);//    printf("%d ", dis[i][j]);num[++maxn] = dis[i][j];}//printf("\n");
    }
}
void build(int mid){int i, j;dlx.init(n);for(i = 1; i <= n; i++){for(j = 1; j <= n; j++){if(dis[i][j] <= mid)     dlx.add(i, j);}}
}int main(void){int TC, i;int low, mid, ans, high;scanf("%d", &TC);while(TC--){scanf("%d%d", &n, &m);for(i = 1; i <= n; i++){scanf("%d%d", &p[i].x, &p[i].y);}maxn = 0;    cal();sort(num + 1, num + 1 + maxn);
//        for(i = 1; i <= maxn; i++) printf("%d\n", num[i]);
    maxn = unique(num+1, num+1+maxn)-num;//    printf("%d\n", maxn);low = 1;    high = maxn-1;while(low <= high){mid = (low+high)>>1;build(num[mid]);if(dlx.dfs(0)){ans = num[mid];high = mid -1;}else low = mid + 1;}printf("%.6f\n", sqrt((double)ans));}return 0;
}

View Code

HDU 2518?

題意：http://acm.hdu.edu.cn/showproblem.php?pid=2518

就是用如圖的圖形，可以旋轉，對稱，排出n*m的矩形(n * m == 60)

問方案數

對12個圖形和60個格子為列。對于每個圖形，打表每個圖形每種樣子覆蓋一個5個格子的方案為一行，對第i圖形的方案第i列為1，覆蓋的5個格子列為1.

跑DLX..

很慢。。。所以打個表。。。

//解釋一個下面打表的程序，每個圖形以第一行最左端為第一個位置，按行從上到下，列從左到右的順序寫出其他位置相對第一個位置的偏移。

//因為*/會把前面的注釋取消掉。。強行變成了下面這個樣子交上去。。。

/*
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;#define N 88
#define M 140
#define INF 0x3f3f3f3f
#define T 420000
int kind[12] = {4, 2, 1, 4, 8, 4, 8, 4, 8, 4, 8, 8};
int row;
int gox[12][8][4] = {{   /******0          0      000         0000          0        0         0000      000        0         0********{1,2,2,2},  {1,2,2,2}, {0,0,1,2}, {0,0,1,2}},{   /******00000    00000           ********{0,0,0,0},{1,2,3,4}},{   /******00000         ********{1, 1, 1, 2}},{   /******0 0       000       00      00000       0 0       0        000      00********{0,1,1,1},{0,0,1,1},{0,1,2,2},{0,1,2,2}},{   /******0           00      0000        00000        0          0        00                   00                  00********{1,1,1,1}, {0,1,2,3},{0,0,0,1},{1,2,3,3},/******00                   00000        0          0        00           0       0000        00                   00********{0,0,0,1},{0,1,2,3},{1,1,1,1},{1,2,3,3}},{/******0           00      00         000         00        00       0000        0          0      00*******{1,1,2,2},{0,1,1,2},{0,1,1,2},{1,1,2,2}},{/******0            0        0000        0          0        0       0000            00000          00         0         0        0000       0        0             000                   00                   00                      00                    0                   0                       0********{1,1,1,1},{1,1,2,3}, {0,0,0,1}, {1,2,2,3}, {1,1,1,1},{1,2,2,3},{0,0,0,1},{1,1,2,3}},{/******0       00          0          00000        0          000        00          00           0       00********{1,1,1,2},{0,1,2,2}, {1,1,1,2},{0,1,2,2}},{/******0      0          00       0           0        0      00      000     000       00       000         00      000       00    00000       0         0         0          00      0        0     0******** /{1,1,2,2},{1,1,1,2},{0,1,1,2},{1,1,1,2},{1,1,2,2},{1,1,1,2},{0,1,1,2},{1,1,1,2}},{/******0           000         0           00            0        000           000000           0          0           0******** /{1,2,2,2}, {0,0,1,2}, {1,1,1,2}, {1,1,1,2}},{/******00      0       000         00          00          0       000       00000      00      00          00          000        00        00       0000                   0                     00                 0***** /{0,1,1,1},{1,1,2,2},{0,0,1,1},{0,1,1,2},{0,1,1,1}, {1,1,2,2},{0,0,1,1},{0,1,1,2}},{/******000        0         00         0        000           0       00        000          00      000          0          00         00        000      00                   00                    0                 000                    0                    0                 0******* /{0,0,1,1},{1,1,2,3}, {0,1,1,1},{1,2,2,3},{0,0,1,1},{1,1,2,3}, {0,1,1,1},{1,2,2,3}}
};
int goy[12][8][4] = {{   /******0          0      000         0000          0        0         0000      000        0         0******** /{0,0,1,2},  {0,-2,-1,0}, {1,2,2,2}, {1,2,0,0}},{   /******00000    00000           ******** /{1,2,3,4},{0,0,0,0}},{   /******00000         ******** / {-1,0,1,0}},{   /******0 0       000       00      00000       0 0       0        000      00******** /{2,0,1,2},{1,2,0,2},{1,0,0,1},{1,1,0,1}},{   /******0           00      0000        00000        0          0        00                   00                  00******** /{0,1,2,3},{1,0,0,0},{1,2,3,3}, {0,0,-1,0},/******00                   00000        0          0        00           0       0000        00                   00******** /{1,2,3,0},{1,1,1,1},{-3,-2,-1,0},{0,0,0,1}},{/******0           00      00         000         00        00       0000        0          0      00******** /{0,1,1,2},{1,-1,0,-1},{1,1,2,2},{-1,0,-2,-1}},{/******0            0        0000        0          0        0       0000            00000          00         0         0        0000       0        0             000                   00                   00                      00                    0                   0                       0******** /{-1,0,1,2},{0,1,0,0},{1,2,3,2},{0,-1,0,0},{-2,-1,0,1},{0,0,1,0},{1,2,3,1},{-1,0,0,0}},{/******0       00          0          00000        0          000        00          00           0       00******** /{-2,-1,0,-2},{1,1,1,2},{0,1,2,2},{1,0,-1,0}},{/******0      0          00       0           0            0          00      000     000       00       000         00          000           00    00000       0         0         0          00          0            0     0******** /{0,1,-1,0},{0,1,2,1},{1,-1,0,0},{-1,0,1,1},{-1,0,0,1},{-2,-1,0,-1},{1,1,2,1},{-1,0,1,-1}},{/******0           000         0           00            0        000           000000           0          0           0******** /{0,-1,0,1},{1,2,1,1},{-2,-1,0,0},{0,1,2,0}},{/******00      0       000         00          00          0       000       00000      00      00          00          000        00        00       0000                   0                     00                 0***** /{1,-1,0,1},{0,1,0,1},{1,2,0,1},{1,0,1,1},{1,0,1,2},{-1,0,-1,0},{1,2,1,2},{1,0,1,0}},{/******000        0         00         0        000           0       00        000          00      000          0          00         00        000      00                   00                    0                 000                    0                    0                 0******** /{1,2,-1,0},{0,1,1,1},{1,-2,-1,0},{0,0,1,1},{1,2,2,3},{-1,0,-1,-1},{1,1,2,3},{0,-1,0,-1}}
};int ans ;struct DLX{int l[T], r[T], u[T], d[T];int col[T], cnt[N], head[T];int id, n;void init(int nt){this->n = nt;int i;for(i = 0; i <= n; i++){d[i] = u[i] = i;l[i] = i - 1; r[i] = i + 1;}l[0] = n; r[n] = 0;memset(cnt, 0, sizeof(cnt));memset(head, -1, sizeof(head));id=  n +1;}void add(int x, int y){u[id] = u[y]; d[id] = y;d[u[y]] = id; u[y] = id;if(head[x] == -1){head[x] = l[id] = r[id] = id;}else{r[id] = r[head[x]]; l[id] = head[x];l[r[id]] = id;  r[l[id]] = id;head[x] = id;}cnt[y] ++;  col[id] = y;id++;}void del(int x){int i, j;l[r[x]] = l[x]; r[l[x]] = r[x];for(i = d[x]; i != x; i = d[i]){for(j = r[i]; j != i; j = r[j]){cnt[col[j]] --;u[d[j]] = u[j]; d[u[j]] = d[j];}}}void resume(int x){int i, j;for(i = u[x]; i != x; i = u[i]){for(j = l[i]; j != i; j = l[j]){cnt[col[j]] ++;d[u[j]] = j;    u[d[j]] = j;}}l[r[x]] = x;    r[l[x]] = x;}void dfs(){if(r[0] == 0)   {ans++;  return;}int idx, temp, i, j;temp = INF;for(i = r[0]; i != 0; i = r[i]){if(cnt[i] < temp){temp = cnt[i];idx = i;}}if(temp == 0) return;del(idx);for(i = d[idx]; i != idx; i = d[i]){for(j = r[i]; j != i; j = r[j]){del(col[j]);}dfs();for(j = l[i]; j != i; j = l[j]){resume(col[j]);}}resume(idx);}
}dlx;int n, m;
void color(int domi, int ang, int x, int y){int i, j, xx, yy;for(i = 0; i < 4; i++){xx = x + gox[domi][ang][i];yy = y + goy[domi][ang][i];if(xx < 1 || xx > n || yy < 1 || yy > m) return;}dlx.add(++row, domi+1);dlx.add(row, m*(x-1)+y+12);for(i = 0; i < 4; i++){xx = x + gox[domi][ang][i];yy = y + goy[domi][ang][i];dlx.add(row, m*(xx-1)+yy+12);}
}int dabiao[10];
int main(void){
//freopen("in", "r", stdin);int x,y,j, i;char map[20][20];/*while(scanf("%d", &n)){for(i = 0; i < kind[n]; i++){memset(map, 1, sizeof(map));map[1][10] = '*';for(j = 0; j < 4; j++){x = 1 + gox[n][i][j];y = 10 + goy[n][i][j];map[x][y] = '*';}for(j = 1; j <= 5; j++){for(int k = 5; k <= 15; k++){printf("%c",map[j][k]);}printf("\n");}printf("\n");}}* /for(n = 1; n <=6; n ++){// while(scanf("%d", &n) != EOF){m = 60/n;ans = 0;    row = 0;dlx.init(72);for(i = 0; i < 12; i++){for(j = 0; j < kind[i]; j++){for(x=1; x <= n; x++){for(y = 1; y <= m; y++){color(i,j,x,y);}}}}dlx.dfs();dabiao[i] = ans;printf("%d %d\n",n, ans / 4);}return 0;}
*/#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;int ans[10] = {0, 0, 0, 2, 368, 1010, 2339};
int main(){int n, m;while(cin>>n>>m){if( n > m) swap(n, m);cout<<ans[n]<<endl;}return 0;
}