Dancing Links 算法学习小结（续2）

LBoy posted @ 2011年2月27日 20:33 in Algorithm Study , 1518 阅读

Fire station   Radar

LBOY: 两个题目是同一个类型，用到的解题思想都是：二分答案 + DLX 判定！以第二个题目为例来说一下。

题目中限制条件，每个消防站可以供应几户人家，如果把消防站看成是行，将用户看成是列，那么问题就是一个“重复覆盖”的模型。因此这里认为每个消防站是和用户相邻的，那么，可以认为用户就是消防站所在地儿。对于给定的最大距离，如果某消防站可以覆盖到某用户，那么就建一个节点。这样构造一个50*50的0-1矩阵。至于最大距离的判断，可以二分来枚举，最大距离，肯定是用户之间的最远距离。但是这样的枚举对于这题是过不去的，需要结构优化：

  1. 二分枚举长度的时候，枚举已经给定的用户之间的距离。（最后的最长距离也肯定在这里面）这就需要记录下任意两个用户之间的距离，进行排序之后，剔除重复的。然后该枚举长度为枚举长度的下表。
  2. 如果存在某一列没有消防站覆盖，即d[x].S == 0, 那么直接返回false.因为这样不满足没咧值至少为1的条件。
  3. 如果M >= N ，那么直接输出0.就可以了。因为每个用户都可以分配到一个用户。

Radar 的优化没用到第一个条件，时间比较长，就补贴了。

 link: http://acm.hdu.edu.cn/showproblem.php?pid=3656    http://acm.hdu.edu.cn/showproblem.php?pid=2295

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

#define arr         100
#define brr         arr*arr
#define head        0
#define inf         1 << 30

struct Point {
    int x, y;
    void in() {
        scanf("%d %d", &x, &y);
    }
    int dis2(const Point &p) {
        return (x-p.x)*(x-p.x) + (y-p.y)*(y-p.y);
    }
}h[arr], f;

struct node {
    int S, C;
    int R, L, U, D;
}d[brr];

int N, M;
int limit, flg, use[arr];
int dist[arr][arr];
int dis[arr*arr], dn;

int H() {
    int ret = 0;
    //memset(use, 0, sizeof(use));
    for (int i = 0; i <= N+1; i++) use[i] = 0;
    for (int t = d[head].R; t != head; t = d[t].R) {
        if (use[t] == false) {
            use[t] = true; ret ++;
            for (int i = d[t].D; i != t; i = d[i].D) {
                for (int j = d[i].R; j != i; j = d[j].R) {
                    use[d[j].C] = true;
                   // if (d[j].C == head) break;
                }
            }
        }
    }
   // printf("ret = %d\n", ret);
    return ret;
}
void remove(const int &c) {
    for (int i = d[c].D; i != c; i = d[i].D) {
        d[d[i].L].R = d[i].R;
        d[d[i].R].L = d[i].L;
        d[d[i].C].S--;
    }
}
void resume(const int &c) {
    for (int i = d[c].U; i != c; i = d[i].U) {
        d[d[i].L].R = i;
        d[d[i].R].L = i;
        d[d[i].C].S++;
    }
}
bool dfs(const int &k) {
    if (k + H() > M) {
        return false;
    }
    if (d[head].R == head) {
        return true;
    }
    int s = inf, c = 1;
    for (int t = d[head].R; t != head; t = d[t].R) {
        if(s > d[t].S) {
            s = d[t].S;
            c = t;
        }
    }
    for (int i = d[c].D; i != c; i = d[i].D) {
        remove(i);
        for (int j = d[i].R; j != i; j = d[j].R) {
            remove(j);
        }
        if (dfs(k + 1)) {
            return true;
        }
        for (int j = d[i].L; j != i; j = d[j].L) {
            resume(j);
        }
        resume(i);
    }
    return false;
}
bool check(int di) {
    d[head].L = N; d[head].R = 1;
    for (int j = 1; j <= N; j++) {
        d[j].S = 0;      d[j].C = j;
        d[j].L = j - 1;  d[j].R = j + 1;
        d[j].U = d[j].D = j;
    }
    d[N].R = head;
    int nod = N, one;
    for (int i = 1; i <= N; i++) {
        one = nod + 1;
        for (int j = 1; j <= N; j++) {
            if (dist[i][j] <= di) {
                d[j].S++; ++nod;  d[nod].C = j;
                d[nod].L = nod - 1; d[nod].R = nod + 1;
                d[nod].U = d[j].U;  d[nod].D = j;
                d[d[j].U].D = nod;  d[j].U = nod;
            }
        }
        if (one <= nod) {
            d[one].L = nod;
            d[nod].R = one;
        }
    }
    for (int i = 1; i <= N; i++) {
        if (d[i].S == 0) return false;
    }
    return dfs(0);
}
void bSearch(int mn, int mx) {
    int md;
    while(mn < mx) {
        md = (mn + mx) >> 1;
        if (check(dis[md])) {
            mx = md ;
        } else {
            mn = md + 1;
        }
    }
    printf("%lf\n", sqrt(1.0*dis[mx]));
}
int main() {
    //freopen("in.in", "r", stdin);
    int ca; scanf("%d", &ca);
    while(ca-- && scanf("%d %d", &N, &M)) {
        dn = 0;
        for (int i = 1; i <= N; i++) {
            h[i].in();
            for (int j = 1; j < i; j++) {
                dist[i][j] = dist[j][i] = h[i].dis2(h[j]);
                dis[dn++] = dist[i][j];
            }
        }
        if (M >= N) {
            printf("%lf\n", 0);
            continue;
        }
        sort(dis, dis + dn);
        int k = 0;
        for (int i = 1; i < dn; i++) {
            if (dis[i] != dis[k]) {
                dis[++k] = dis[i];
            }
        }
        bSearch(0, k);
    }
    return 0;
}

 

Bomberman - Just Search!

炸弹人游戏，在空地上放置最少的炸弹来炸掉所有的可炸的墙。

先找题目中的限制条件

  1. 每个炸弹可以放置在空地上，向四个方向爆破，爆破的半径是无限的。
  2. 每个墙可能被多个炸弹攻击。
  3. 所有的空地是联通的，也就是说至少存在一组可行解。

上面的第二个条件是重要的，这提示我们用“重复覆盖”的方法来解决，下面要做的就是向重复模型转化了。将每个空位看成行，每个可爆破的墙看成是列。为了方便，我们可以将所有的墙进行列序优先的编号。剩下的就是“套模板”了。

link: http://acm.hdu.edu.cn/showproblem.php?pid=3529

#include <iostream>
using namespace std;

#define arr         225
#define brr         arr*arr
#define head        0
#define inf         1 << 30

struct node {
    int S, C;
    int R, L, U, D;
}d[brr];

int n, m, M;
char mat[16][16];
int col[16][16];
void insert(int &nod, int id) {
    d[++nod].C = id;     d[id].S++;
    d[nod].L = nod - 1;  d[nod].R = nod + 1;
    d[nod].U = d[id].U;  d[nod].D = id;
    d[d[id].U].D = nod;  d[id].U = nod; 
}
int stp[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
inline bool islegal(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m && mat[x][y] != '*';
}
void insert(int x, int y, int &nod) {
    int one = nod + 1, id, nx, ny;    
    for (int k = 0; k < 4; k++) {        
        nx = x + stp[k][0];
        ny = y + stp[k][1];
        id = -1;
        while(islegal(nx, ny) == true) {
            if (mat[nx][ny] == '#') {
                id = col[nx][ny];
                break;
            }
            nx = nx + stp[k][0];
            ny = ny + stp[k][1];
        }
        if (id != -1) {
            insert(nod, id);
           // printf("(%d, %d)->(%d, %d)\n", x, y, nx, ny);
        }
    }
    if (one <= nod) {
        d[one].L = nod;
        d[nod].R = one;
    }
}
int limit, use[arr];
int h() {
    int ret = 0;
    memset(use, 0, sizeof(use));
    for (int t = d[head].R; t != head; t = d[t].R) {
        if (use[t] == false) {
            use[t] = true; ret ++;
            for (int i = d[t].D; i != t; i = d[i].D) {
                for (int j = d[i].R; j != i; j = d[j].R) {
                    use[d[j].C] = true;
                }
            }
        }
    }
   // cout << "ret = " << ret << endl;
    return ret;
}
void remove(const int &c) {
    for (int i = d[c].D; i != c; i = d[i].D) {
        d[d[i].R].L = d[i].L;
        d[d[i].L].R = d[i].R;
    }
}
void resume(const int &c) {
    for (int i = d[c].U; i != c; i = d[i].U) {
        d[d[i].R].L = i;
        d[d[i].L].R = i;
    }
}

bool dfs(const int &k) {
    if (k + h() >= limit) {        
        return false;
    }
    if (d[head].R == head) {
        if (k < limit) limit = k;
        return true;
    }
    int s = inf, c;
    for (int t = d[head].R; t != head; t = d[t].R) {
        if (s > d[t].S) {
            s = d[t].S;
            c = t;
        }
    }   
    for (int i = d[c].D; i != c; i = d[i].D) {
        remove(i);
        for (int j = d[i].R; j != i; j = d[j].R) {
            remove(j);
        }
        if (dfs(k + 1)) {
            return true;
        }
        for (int j = d[i].L; j != i; j = d[j].L) {
            resume(j);
        }
         resume(i);
    }
    return false;
}
int main() {
    //freopen("in.in", "r", stdin);
    while(scanf("%d %d", &n, &m) != EOF) {
        M = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%s", mat[i] + 1); 
            for (int j = 1; j <= m; j++) {
                if(mat[i][j] == '#') {
                    col[i][j] = ++M;
                }               
            }
        }
        d[head].L = M; d[head].R = 1;
        for (int j = 1; j <= M; j++) {
            d[j].L = j - 1; d[j].R = j + 1;
            d[j].U = j;     d[j].D = j;
            d[j].C = 1;     d[j].S = 0;
        }
        d[M].R = head;
        int nod = M;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (mat[i][j] == '.') {
                    insert(i, j, nod);
                }
            }
        }
       // printf("nod = %d\n", nod);
        limit = h();
        while(dfs(0) == false) limit++;
        printf("%d\n", limit);
    }
    return 0;
}

神龙的难题

LBOY: 问题中的限制条件：

  1. 每个位置都可以放置炸弹
  2. 每个位置可以被多个爆破
  3. 每次的攻击范围可认为是将炸弹放置在左上角。

上面的第二个条件使我们要找的，建模+（重复覆盖）。以每个位置为行（1），恶魔所在的位置（进行列序优先的编号）为列。这样得到一个(N*N)*(N*N)的0-1矩阵。

 link: http://acm.fzu.edu.cn/problem.php?pid=1686

#include <iostream>
using namespace std;

#define arr         16
#define brr         256
#define crr         arr * brr
#define head        0
#define inf         1 << 30

int n, m, N, M, r, c;
int mat[arr][arr];
struct node {
    int S, C;
    int L, R, U, D;
}d[crr];

int limit, flg, use[brr];
int h() {
    int ret = 0;
    memset(use, 0, sizeof(use));
    for (int t = d[head].R; t != head; t = d[t].R) {
        if (use[t] == false) {
            use[t] = true; ret ++;
            for (int i = d[t].D; i != t; i = d[i].D) {
                for (int j = d[i].R; j != i; j = d[j].R) {
                    use[d[j].C] = true;
                }
            }
        }
    }
   // printf("ret = %d\n", ret);
    return ret;
}
void remove(const int &c) {
    for (int i = d[c].D; i != c; i = d[i].D) {
        d[d[i].L].R = d[i].R;
        d[d[i].R].L = d[i].L;
    }
}
void resume(const int &c) {
    for (int i = d[c].U; i != c; i = d[i].U) {
        d[d[i].L].R = i;
        d[d[i].R].L = i;
    }
}
int dfs(const int &k) {
    if (k + h() > limit) {
        return k + h();
    }
    if (d[head].R == head) {
        flg = true;
        return k;
    }
    int s = inf, c;
    for (int t = d[head].R; t != head; t = d[t].R) {
        if(s > d[t].S) {
            s = d[t].S;
            c = t;
        }
    } //printf("k = %d\n", k);
    int tmp, nxt = inf;
    for (int i = d[c].D; i != c; i = d[i].D) {
        remove(i);
        for (int j = d[i].R; j != i; j = d[j].R) {
            remove(j);
        }
        tmp = dfs(k + 1);
        if (flg == true) {
            return tmp;
        }
        nxt = min(nxt, tmp);
        for (int j = d[i].L; j != i; j = d[j].L) {
            resume(j);
        }
        resume(i);
    }
    return nxt;
}

int id_astar() {
    limit = h();
    flg = false;
    while(flg == false) {
        limit = dfs(0);
      // printf("limit = %d\n", limit);
    }
    return limit;
}
int main() {
    while(scanf("%d %d", &n, &m) != EOF) {
        M = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%d", mat[i] + j);
                if (mat[i][j] == 1) {
                    mat[i][j] = -(++M);
                }
            }
        }
        scanf("%d %d", &r, &c);
        d[head].L = M; d[head].R = 1;
        for (int j = 1; j <= M; j++) {
            d[j].S = 0; d[j].C = j;
            d[j].L = j - 1; d[j].R = j + 1;
            d[j].U = d[j].D = j;
        }
        d[M].R = head;
        int nod = M, one, id;
        for (int i = 1; i <= n - r + 1; i++) {
            for (int j = 1; j <= m - c + 1; j++) {
                one = nod + 1;
                for (int p = i; p < i + r; p++) {
                    for (int q = j; q < j + c; q++) {
                        if (mat[p][q] < 0) {
                            id = -mat[p][q];
                            d[id].S++; ++nod;   d[nod].C = id;
                            d[nod].L = nod - 1; d[nod].R = nod + 1;
                            d[nod].U = d[id].U; d[nod].D = id;
                            d[d[id].U].D = nod; d[id].U = nod;
                        }
                    }
                }
                if (one <= nod) {
                    d[one].L = nod;
                    d[nod].R = one;
                }
            }
        }
        printf("%d\n", id_astar());
    }
    return 0;
}

 

 

  • 无匹配
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1