首页 > ACM题库 > HDU-杭电 > HDU 3498-whosyourdaddy-回溯和剪枝-[解题报告]HOJ
2014
04-09

HDU 3498-whosyourdaddy-回溯和剪枝-[解题报告]HOJ

whosyourdaddy

问题描述 :

sevenzero liked Warcraft very much, but he haven’t practiced it for several years after being addicted to algorithms. Now, though he is playing with computer, he nearly losed and only his hero Pit Lord left. sevenzero is angry, he decided to cheat to turn defeat into victory. So he entered "whosyourdaddy", that let Pit Lord kill any hostile unit he damages immediately. As all Warcrafters know, Pit Lord masters a skill called Cleaving Attack and he can damage neighbour units of the unit he attacks. Pit Lord can choice a position to attack to avoid killing partial neighbour units sevenzero don’t want to kill. Because sevenzero wants to win as soon as possible, he needs to know the minimum attack times to eliminate all the enemys.

输入:

There are several cases. For each case, first line contains two integer N (2 ≤ N ≤ 55) and M (0 ≤ M ≤ N*N),and N is the number of hostile units. Hostile units are numbered from 1 to N. For the subsequent M lines, each line contains two integers A and B, that means A and B are neighbor. Each unit has no more than 4 neighbor units. The input is terminated by EOF.

输出:

There are several cases. For each case, first line contains two integer N (2 ≤ N ≤ 55) and M (0 ≤ M ≤ N*N),and N is the number of hostile units. Hostile units are numbered from 1 to N. For the subsequent M lines, each line contains two integers A and B, that means A and B are neighbor. Each unit has no more than 4 neighbor units. The input is terminated by EOF.

样例输入:

5 4
1 2
1 3
2 4
4 5
6 4
1 2
1 3
1 4
4 5

样例输出:

2
3

有n个单位的敌人,对某个敌人进行攻击时该敌人以及与其直接相邻的敌人都会被消灭。问消灭所有敌人所需的最少攻击次数。

重复覆盖问题。我把此题贴出来是想说剪枝优化很有必要,一个小细节就能决定是TLE还是AC。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath> 

using namespace std;

const int maxn = 60*60 + 10;
const int oo = 1 << 30;
const int maxrow = 60;
const int maxcol = 60;
int mtx[maxrow][maxcol];
int n, m, ans;

int totRow, totCol, head, idx;
int L[maxn], R[maxn], U[maxn], D[maxn];
int RH[maxn], CH[maxn], S[maxn];

void initMtx()
{
    memset(mtx, 0, sizeof(mtx));
    for (int i = 0; i < n; ++i) {
        mtx[i][i] = 1;
    }
    int a, b;
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", &a, &b);
        a--; b--;
        mtx[a][b] = mtx[b][a] = 1;
    }
}

int newNode(int up, int down, int left, int right)
{
    U[idx] = up;    D[idx] = down;
    L[idx] = left;  R[idx] = right;
    U[down] = D[up] = L[right] = R[left] = idx;
    return idx++;
}

void build()
{
    idx = maxn - 1;
    head = newNode(idx, idx, idx, idx);
    idx = 0;
    for (int j = 0; j < totCol; ++j) {
        newNode(idx, idx, L[head], head);
        CH[j] = j;  S[j] = 0;
    }
    for (int i = 0; i < totRow; ++i) {
        int k = -1;
        for (int j = 0; j < totCol; ++j) {
            if (!mtx[i][j]) continue;
            if (-1 == k) {
                k = newNode(U[CH[j]], CH[j], idx, idx);
                RH[k] = i;  CH[k] = j;  S[j]++;
            } else {
                k = newNode(U[CH[j]], CH[j], k, R[k]);
                RH[k] = i;  CH[k] = j;  S[j]++;
            }
        }
    }
}

void remove(int c)
{
    for (int i = D[c]; i != c; i = D[i]) {
        L[R[i]] = L[i]; R[L[i]] = R[i]; /*S[CH[i]]--;*/
    }
}

void resume(int c)
{
    for (int i = U[c]; i != c; i = U[i]) {
        L[R[i]] = R[L[i]] = i; /*S[CH[i]]++;*/ 
    }
}

/*估价函数*/
int h()
{
    bool vis[maxcol];
    memset(vis, false, sizeof(vis));
    int ret = 0;
    for (int i = R[head]; i != head; i = R[i]) {
        if (!vis[i]) {
            ret++;
            vis[i] = true;
            for (int j = D[i]; j != i; j = D[j]) {
                for (int k = R[j]; k != j; k = R[k]) {
                    vis[CH[k]] = true;
                }
            }
        }
    }
    return ret;
}

void dance(int cnt)
{
    if (cnt + h() >= ans) { //此处写成">"会TLE
        return ;
    }
    if (R[head] == head) {
        ans = cnt;
        return ;
    }
    int c, Min = oo;
    for (int i = R[head]; i != head; i = R[i]) {
        if (S[i] < Min) {
            Min = S[i]; c = i;
        }
    }
    for (int i = D[c]; i != c; i = D[i]) {
        remove(i);
        for (int j = R[i]; j != i; j = R[j]) {
            remove(j);
        } 
        
        dance(cnt + 1);
        
        for (int j = L[i]; j != i; j = L[j]) {
            resume(j);
        }
        resume(i);
    }
    return ; 
}

int main()
{
    while (scanf("%d%d", &n, &m) != EOF) {
        totRow = n; totCol = n; 
        initMtx();
        build();
        ans = oo;
        dance(0);
        printf("%d\n", ans);
    } 
    return 0;
}

参考:http://blog.csdn.net/ahfywff/article/details/7940737


  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  3. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  4. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥