列表

详情

NC17514. [NOI2007]追捕盗贼

描述

魔法国度Magic Land里最近出现了一个大盗Frank，他在Magic Land四处作案，专门窃取政府机关的机密文件（因而有人怀疑Frank是敌国派来的间谍）。
为了捉住Frank，Magic Land的安全局重拳出击！
Magic Land由N个城市组成，并且这N个城市又由恰好N-1条公路彼此连接起来，使得任意两个城市间都可以通过若干条公路互达。从数据结构的角度我们也可以说，这N个城市和N-1条公路形成了一棵树。
例如，下图就是Magic Land的一个可能格局（4个城市用数字编号，3条公路用字母编号）：

大盗Frank能够在公路上以任意速度移动。
比方说，对于上图给出的格局，在0.00001秒钟内（或者任意短的一段时间内），Frank就可以从城市1经过城市2到达城市4，中间经过了两条公路。
想要生擒Frank困难重重，所以安全局派出了经验丰富的警探，这些警探具有非凡的追捕才能：
1. 只要有警探和Frank同处一个城市，那么就能够立刻察觉到Frank，并且将其逮捕。
2. 虽然Frank可以在公路上以任意快的速度移动，但是如果有警探和Frank在同一条公路上相遇，那么警探也可以立刻察觉到Frank并将其逮捕。
安全局完全不知道Frank躲在哪个城市，或者正在哪条公路上移动，所以需要制定一个周密的抓捕计划，计划由若干步骤组成。在每一步中，可以做如下几件事中的一个：
1. 在某个城市空降一位警探。警探可以直接从指挥部空降到Magic Land的任意一个城市里。此操作记为“L x”，表示在编号为x的城市里空降一位警探。耗时1秒。
2. 把留在某个城市里的一位警探直接召回指挥部。以备在以后的步骤中再度空降到某个城市里。此操作记为“B x”。表示把编号为x的城市里的一位警探召回指挥部。耗时1秒。
3. 让待在城市x的一位警探沿着公路移动到城市y，此操作记为“M x y”。耗时1秒。当然，前提是城市x和城市y之间有公路。如果在警探移动的过程中，大盗Frank也在同一条公路上，那么警探就抓捕到了Frank。
现在，由你来制定一套追捕计划，也就是给出若干个步骤，需要保证：无论大盗Frank一开始躲在哪儿，也无论Frank在整个过程中如何狡猾地移动 （Frank大盗可能会窃取到追捕行动的计划书，所以他一定会想尽办法逃避），他一定会被缉拿归案。
希望参与的警探越少越好，因为经验丰富的警探毕竟不多。
例如对于前面所给的那个图示格局，一个可行的计划如下：
1. L 2 在城市2空降一位警探。注意这一步完成之后，城市2里不会有Frank，否则他将被捉住。
2. L 2 再在城市2空降一位警探。
3. M 2 1 让城市2的一位警探移动到城市1。注意城市2里还留有另一位警探。这一步完成之后，城市1里不会有Frank，公路A上也
不会有Frank。也就是说，假如Frank还没有被逮捕，那么他只能是在城市3或城市4里，或者公路B或公路C上。
4. B 1 召回城市1的一位警探。注意虽然召回了这位警探，但是由于我们始终留了一位警探在城市2把守，所以Frank仍然不可能跑到
城市1或者是公路A上。
5. L 3 在城市3空降一位警探。注意这一步可以空降在此之前被召回的那位警探。这一步完成之后，城市3里不会有Frank，否则他会被捉住。
6. M 3 2 让城市3里的一位警探移动到城市2。这一步完成之后，如果Frank还没有被捉住，那他只能是在公路C上或者城市4里。注意
这一步之后，城市2里有两位警探。
7. M 2 4 让城市2里的一位警探移动到城市4。这一步完成之后，Frank一定会被捉住，除非他根本就没来Magic Land。
这个计划总共需要2位警探的参与。可以证明：如果自始至终只有1名或者更少的警探参与，则Frank就会逍遥法外。

你的任务很简单：对于一个输入的Magic Land的格局，计算S，也就是为了追捕Frank至少需要投入多少位警探，并且给出相应的追捕计划步骤。

对于任何一个测试点：
如果输出的追捕计划不合法，或者整个追捕计划的步骤数 T 超过了 20000，或者追捕计划结束之后，不能保证捉住 Frank，则不能得分。
否则，用你输出的 S 和我们已知的标准答案 S * 相比较：
1. 若 S<S * ，则得到 120%的分。
2. 若 S=S * ，则得到 100%的分。
3. 若 S * <S≤S * +2，则得到 60%的分。
4. 若 S * +2<S≤S * +4，则得到 40%的分。
5. 若 S * +4<S≤S * +8，则得到 20%的分。
6. 若 S>S * +8，则得到 10%的分。
输入保证描述了一棵连通的 N 结点树，1≤N≤1 000。

输入描述

输入给出了Magic Land的格局。
第一行一个整数N，代表有N个城市，城市的编号是1~N。
接下来N-1行，每行有两个用空格分开的整数xi，yi，代表城市xi，yi之间有公路相连。保证1≤xi,yi≤N

输出描述

输出你所给出的追捕计划。
第一行请输出一个整数S，代表追捕计划需要多少位警探。
第二行请输出一个整数T，代表追捕计划总共有多少步。
接下来请输出T行，依次描述了追捕计划的每一步。每行必须是以下三种形式之一：
z“L x”，其中L是大写字母，接着是一个空格，再接着是整数x，代表在城市x空降一位警探。你必须保证1≤x≤N。
z“B x”，其中B是大写字母，接着是一个空格，再接着是整数x，代表召回城市x的一位警探。你必须保证1≤x≤N，且你的计
划执行到这一步之前，城市x里面确实至少有一位警探。
z“M x y”，其中M是大写字母，接着是一个空格，再接着是整数x，再跟一个空格，最后一个是整数y。代表让城市x的一位警
探沿着公路移动到城市y。你必须保证1≤x, y≤N，且你的计划执行到这一步之前，城市x里面确实至少有一位警探，且城市x, y之前
确实有公路。
必须保证输出的S确实等于追捕计划中所需要的警探数目。

示例1

输入: 

4 
1 2
3 2
2 4

输出: 

2
11
L 2
L 2
M 2 1
B 1
L 2
M 2 3
B 3
L 2
M 2 4
B 4
B 2

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 33ms, 内存消耗: 12668K, 提交时间: 2020-03-29 17:21:11 

#include <cstdio>
#include <cassert>
#include <cstring>
 
#define MAXN 2000
 
#define MAXT 40000
 
struct Edge {
    int x, y;
    int invalid;
     
    int valid()
    {
        return !invalid;
    }
     
    int other_from(int u)
    {
        if (invalid) {
            return -1;
        }
        if (u==x) {
            return y;
        } else if (u==y) {
            return x;
        }
 
        return -1;
    }
};
 
enum Type {
    Hub,
    Ending,
    Internal,
    Midst
};
 
struct Info {
    Type type;
    int s;
    int av_start, av_end;
    Info * m_info;
};
 
struct Step {
    char cmd; // 'L' 'B' 'M'
    int u;
    int v;
};
 
int T; // number of steps
Step steps[MAXT+1];
 
int n;
 
int main_s_output;
 
int deg[MAXN+1];
Edge edges[MAXN+1];
Edge * graph[MAXN+1][MAXN+1];
int dist[MAXN+1][MAXN+1];
 
 
void genstep(char cmd, int u, int v)
{
    steps[T].cmd = cmd;
    steps[T].u = u;
    steps[T].v = v;
    ++T;
}
 
void output()
{
    printf( "%d\n", T);
    for (int i=0; i<T; ++i) {
        switch (steps[i].cmd) {
            case 'L': printf("L %d\n", steps[i].u+1);
                      break;
            case 'B': printf( "B %d\n", steps[i].u+1);
                      break;
            case 'M': printf( "M %d %d\n", steps[i].u+1, steps[i].v+1);
                      break;
            default:  assert(0);
                      break;
        }
    }
}
 
void dfs_find_dist(int src, int v, int d)
{
    dist[src][v] = d;
    for (int i=0; i<deg[v]; ++i) {
        int u = graph[v][i]->other_from(v);
        if (dist[src][u]<0) {
            dfs_find_dist(src, u, d+1);
        }
    }
}
 
void init()
{
 
    memset(deg, 0, sizeof(deg));
    memset(edges, 0, sizeof(edges));
 
    scanf("%d", &n);
    for (int i=0; i<n-1; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        --u;
        --v;
        edges[i].x = u;
        edges[i].y = v;
        edges[i].invalid = 0;
 
        graph[u][deg[u]++] = edges+i;
        graph[v][deg[v]++] = edges+i;
    }
 
    main_s_output = 1;
    T = 0;
     
    for (int u=0; u<n; ++u) {
        for (int v=0; v<n; ++v) {
            dist[u][v] = -1;
        }
    }
 
    for (int u=0; u<n; ++u) {
        dfs_find_dist(u, u, 0);
    }
}
 
Info * re_root(Info * info_old, int root, int root_old)
{
    Info * info = new Info;
     
    info->s = info_old->s;
    info->av_start = info_old->av_start;
    info->av_end = info_old->av_end;
 
    switch (info_old->type) {
        case Hub:
        case Ending:
            info->type = Ending;
            break;
        case Internal:
            if (info->s==1) {
                info->type = Ending;
            } else {
                info->type = Midst;
                info->m_info = new Info;
                info->m_info->type = Ending;
                info->m_info->s = 1;
                info->m_info->av_start = root;
                info->m_info->av_end = root_old;
            }
            break;
        case Midst:
   // random cover
            info->type = Midst;
            info->m_info = re_root(info_old->m_info, root, root_old);
            break;
    }
 
    return info;
}
 
int farther(int u, int a, int b)
{
    if (dist[u][b]>dist[u][a]) {
        return b;
    } else {
        return a;
    }
 
    return -1;
}
 
Info * merge(Info * info1, Info * info2, int root)
{
    Info * info = new Info;
 
    info->s = -1;
 
    if (info1->s < info2->s || (info1->s==info2->s && info1->type>info2->type)) {
        Info * tmp = info1;
        info1 = info2;
        info2 = tmp;
    }
 
    if (info1->s == info2->s) {
        if (info1->type==Hub && info2->type==Hub) {
            // Case 1  nocover
            info->type = Hub;
            info->s = info1->s;
            info->av_start = info->av_end = root;
        } else if (info1->type==Hub && info2->type==Ending) {
            // Case 2 random cover
            info->type = Ending;
            info->s = info1->s;
            info->av_start = root;
            info->av_end = farther(root, info2->av_start, info2->av_end);
        } else if (info1->type==Ending && info2->type==Ending) {
            // Case 3
            info->type = Internal;
            info->s = info1->s;
            info->av_start = farther(root, info1->av_start, info1->av_end);
            info->av_end = farther(root, info2->av_start, info2->av_end);
        } else if (info1->type==Hub && info2->type==Internal) {
            // Case 4 nocover
            info->type = Internal;
            info->s = info1->s;
            info->av_start = info2->av_start;
            info->av_end = info2->av_end;
        } else {
            assert( (info1->type==Midst || info2->type==Midst) ||
                    (info1->type==Internal && info2->type==Internal) ||
                    (info1->type==Ending && info2->type==Internal) );
            // Case 5
            info->type = Hub;
            info->s = info1->s+1;
            info->av_start = info->av_end = root;
        }
    } else {
        assert(info1->s > info2->s);
        if (info1->type==Hub || info1->type==Ending || info1->type==Internal) {
            info->type = info1->type;
            info->s = info1->s;
            if (info->type==Hub || info->type==Internal) {
    // random cover
                info->av_start = info1->av_start;
                info->av_end = info1->av_end;
            } else {
                assert(info->type==Ending);
                info->av_start = farther(root, info1->av_start, info1->av_end);
                info->av_end = root;
            }
        } else {
            assert(info1->type == Midst);
            Info * tmp = merge(info1->m_info, info2, root);
            assert(tmp->s <= info1->s);
            if (tmp->s < info1->s) {
                info->type = Midst;
                info->s = info1->s;
                info->m_info = tmp;
                info->av_start = info1->av_start;
                info->av_end = info1->av_end;
            } else {
    // random cover
                info->type = Hub;
                info->s = info1->s+1;
                info->av_start = info->av_end = root;
            }
        }
    }
 
    assert(info->s>0);
 
    return info;
}
 
Info * calc_info(int root)
{
    int d = 0;
    int neighbor_index = -1;
    int neighbor;
    Info * info = NULL;
    for (int i=0; i<deg[root]; ++i) {
        if (graph[root][i]->valid()) {
            ++d;
            neighbor_index = i;
            neighbor = graph[root][i]->other_from(root);
        }
    }
 
    assert(d>0);
 
    if (d==1) {
        d = 0;
        for (int i=0; i<deg[neighbor]; ++i) {
            if (graph[neighbor][i]->valid()) {
                ++d;
            }
        }
        if (d>1) {
            info = re_root(calc_info(neighbor), root, neighbor);
        } else {
            info = new Info;
            info->type = Ending;
            info->s = 1;
            info->m_info = NULL;
            info->av_start = root;
            info->av_end = neighbor;
        }
    } else {
        ++graph[root][neighbor_index]->invalid;
        Info * info1 = calc_info(root);
        --graph[root][neighbor_index]->invalid;
        for (int i=0; i<neighbor_index; ++i) {
            ++graph[root][i]->invalid;
        }
        Info * info2 = calc_info(root);
        for (int i=0; i<neighbor_index; ++i) {
            --graph[root][i]->invalid;
        }
        info = merge(info1, info2, root);
    }
 
    return info;
}
 
void solve(int root)
{
    Info * info = calc_info(root);
    if (main_s_output) {
        main_s_output = 0;
        printf("%d\n", info->s);
    }
    int u = info->av_start;
    int v = info->av_end;
 
    genstep('L', u, 0);
    while (1) {
        int next = -1;
        if (u!=v) {
            for (int i=0; i<deg[u]; ++i) {
                if (graph[u][i]->valid()) {
                    int x = graph[u][i]->other_from(u);
                    if (dist[x][v]+1==dist[u][v]) {
                        ++graph[u][i]->invalid;
                        next = x;
                        break;
                    }
                }
            }
            assert(next>=0);
        }
 
        for (int i=0; i<deg[u]; ++i) {
            ++graph[u][i]->invalid;
        }
 
        for (int i=0; i<deg[u]; ++i) {
            --graph[u][i]->invalid;
            if (graph[u][i]->valid()) {
                solve(u);
            }
            ++graph[u][i]->invalid;
        }
 
        for (int i=0; i<deg[u]; ++i) {
            --graph[u][i]->invalid;
        }
 
        if (next<0) {
            break;
        } else {
            genstep('M', u, next);
            u = next;
        }
    }
    genstep('B', v, 0);
}
 
int main()
{
    init();
    solve(0);
    output();
 
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 50ms, 内存消耗: 12744K, 提交时间: 2019-01-07 17:07:29 

#include <cstdio>
#include <cassert>
#include <cstring>

#define MAXN 2000

#define MAXT 40000

struct Edge {
    int x, y;
    int invalid;
    
    int valid()
    {
        return !invalid;
    }
    
    int other_from(int u)
    {
        if (invalid) {
            return -1;
        }
        if (u==x) {
            return y;
        } else if (u==y) {
            return x;
        }

        return -1;
    }
};

enum Type {
    Hub,
    Ending,
    Internal,
    Midst
};

struct Info {
    Type type;
    int s;
    int av_start, av_end;
    Info * m_info;
};

struct Step {
    char cmd; // 'L' 'B' 'M'
    int u;
    int v;
};

int T; // number of steps
Step steps[MAXT+1];

int n;

int main_s_output;

int deg[MAXN+1];
Edge edges[MAXN+1];
Edge * graph[MAXN+1][MAXN+1];
int dist[MAXN+1][MAXN+1];


void genstep(char cmd, int u, int v)
{
    steps[T].cmd = cmd;
    steps[T].u = u;
    steps[T].v = v;
    ++T;
}

void output()
{
    printf( "%d\n", T);
    for (int i=0; i<T; ++i) {
        switch (steps[i].cmd) {
            case 'L': printf("L %d\n", steps[i].u+1);
                      break;
            case 'B': printf( "B %d\n", steps[i].u+1);
                      break;
            case 'M': printf( "M %d %d\n", steps[i].u+1, steps[i].v+1);
                      break;
            default:  assert(0);
                      break;
        }
    }
}

void dfs_find_dist(int src, int v, int d)
{
    dist[src][v] = d;
    for (int i=0; i<deg[v]; ++i) {
        int u = graph[v][i]->other_from(v);
        if (dist[src][u]<0) {
            dfs_find_dist(src, u, d+1);
        }
    }
}

void init()
{

    memset(deg, 0, sizeof(deg));
    memset(edges, 0, sizeof(edges));

    scanf("%d", &n);
    for (int i=0; i<n-1; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        --u;
        --v;
        edges[i].x = u;
        edges[i].y = v;
        edges[i].invalid = 0;

        graph[u][deg[u]++] = edges+i;
        graph[v][deg[v]++] = edges+i;
    }

    main_s_output = 1;
    T = 0;
    
    for (int u=0; u<n; ++u) {
        for (int v=0; v<n; ++v) {
            dist[u][v] = -1;
        }
    }

    for (int u=0; u<n; ++u) {
        dfs_find_dist(u, u, 0);
    }
}

Info * re_root(Info * info_old, int root, int root_old)
{
    Info * info = new Info;
    
    info->s = info_old->s;
    info->av_start = info_old->av_start;
    info->av_end = info_old->av_end;

    switch (info_old->type) {
        case Hub:
        case Ending:
            info->type = Ending;
            break;
        case Internal:
            if (info->s==1) {
                info->type = Ending;
            } else {
                info->type = Midst;
                info->m_info = new Info;
                info->m_info->type = Ending;
                info->m_info->s = 1;
                info->m_info->av_start = root;
                info->m_info->av_end = root_old;
            }
            break;
        case Midst:
   // random cover
            info->type = Midst;
            info->m_info = re_root(info_old->m_info, root, root_old);
            break;
    }

    return info;
}

int farther(int u, int a, int b)
{
    if (dist[u][b]>dist[u][a]) {
        return b;
    } else {
        return a;
    }

    return -1;
}

Info * merge(Info * info1, Info * info2, int root)
{
    Info * info = new Info;

    info->s = -1;

    if (info1->s < info2->s || (info1->s==info2->s && info1->type>info2->type)) {
        Info * tmp = info1;
        info1 = info2;
        info2 = tmp;
    }

    if (info1->s == info2->s) {
        if (info1->type==Hub && info2->type==Hub) {
            // Case 1  nocover
            info->type = Hub;
            info->s = info1->s;
            info->av_start = info->av_end = root;
        } else if (info1->type==Hub && info2->type==Ending) {
            // Case 2 random cover
            info->type = Ending;
            info->s = info1->s;
            info->av_start = root;
            info->av_end = farther(root, info2->av_start, info2->av_end);
        } else if (info1->type==Ending && info2->type==Ending) {
            // Case 3
            info->type = Internal;
            info->s = info1->s;
            info->av_start = farther(root, info1->av_start, info1->av_end);
            info->av_end = farther(root, info2->av_start, info2->av_end);
        } else if (info1->type==Hub && info2->type==Internal) {
            // Case 4 nocover
            info->type = Internal;
            info->s = info1->s;
            info->av_start = info2->av_start;
            info->av_end = info2->av_end;
        } else {
            assert( (info1->type==Midst || info2->type==Midst) ||
                    (info1->type==Internal && info2->type==Internal) ||
                    (info1->type==Ending && info2->type==Internal) );
            // Case 5
            info->type = Hub;
            info->s = info1->s+1;
            info->av_start = info->av_end = root;
        }
    } else {
        assert(info1->s > info2->s);
        if (info1->type==Hub || info1->type==Ending || info1->type==Internal) {
            info->type = info1->type;
            info->s = info1->s;
            if (info->type==Hub || info->type==Internal) {
    // random cover
                info->av_start = info1->av_start;
                info->av_end = info1->av_end;
            } else {
                assert(info->type==Ending);
                info->av_start = farther(root, info1->av_start, info1->av_end);
                info->av_end = root;
            }
        } else {
            assert(info1->type == Midst);
            Info * tmp = merge(info1->m_info, info2, root);
            assert(tmp->s <= info1->s);
            if (tmp->s < info1->s) {
                info->type = Midst;
                info->s = info1->s;
                info->m_info = tmp;
                info->av_start = info1->av_start;
                info->av_end = info1->av_end;
            } else {
    // random cover
                info->type = Hub;
                info->s = info1->s+1;
                info->av_start = info->av_end = root;
            }
        }
    }

    assert(info->s>0);

    return info;
}

Info * calc_info(int root)
{
    int d = 0;
    int neighbor_index = -1;
    int neighbor;
    Info * info = NULL;
    for (int i=0; i<deg[root]; ++i) {
        if (graph[root][i]->valid()) {
            ++d;
            neighbor_index = i;
            neighbor = graph[root][i]->other_from(root);
        }
    }

    assert(d>0);

    if (d==1) {
        d = 0;
        for (int i=0; i<deg[neighbor]; ++i) {
            if (graph[neighbor][i]->valid()) {
                ++d;
            }
        }
        if (d>1) {
            info = re_root(calc_info(neighbor), root, neighbor);
        } else {
            info = new Info;
            info->type = Ending;
            info->s = 1;
            info->m_info = NULL;
            info->av_start = root;
            info->av_end = neighbor;
        }
    } else {
        ++graph[root][neighbor_index]->invalid;
        Info * info1 = calc_info(root);
        --graph[root][neighbor_index]->invalid;
        for (int i=0; i<neighbor_index; ++i) {
            ++graph[root][i]->invalid;
        }
        Info * info2 = calc_info(root);
        for (int i=0; i<neighbor_index; ++i) {
            --graph[root][i]->invalid;
        }
        info = merge(info1, info2, root);
    }

    return info;
}

void solve(int root)
{
    Info * info = calc_info(root);
    if (main_s_output) {
        main_s_output = 0;
        printf("%d\n", info->s);
    }
    int u = info->av_start;
    int v = info->av_end;

    genstep('L', u, 0);
    while (1) {
        int next = -1;
        if (u!=v) {
            for (int i=0; i<deg[u]; ++i) {
                if (graph[u][i]->valid()) {
                    int x = graph[u][i]->other_from(u);
                    if (dist[x][v]+1==dist[u][v]) {
                        ++graph[u][i]->invalid;
                        next = x;
                        break;
                    }
                }
            }
            assert(next>=0);
        }

        for (int i=0; i<deg[u]; ++i) {
            ++graph[u][i]->invalid;
        }

        for (int i=0; i<deg[u]; ++i) {
            --graph[u][i]->invalid;
            if (graph[u][i]->valid()) {
                solve(u);
            }
            ++graph[u][i]->invalid;
        }

        for (int i=0; i<deg[u]; ++i) {
            --graph[u][i]->invalid;
        }

        if (next<0) {
            break;
        } else {
            genstep('M', u, next);
            u = next;
        }
    }
    genstep('B', v, 0);
}

int main()
{
    init();
    solve(0);
    output();

    return 0;
}

上一题

© 2024 nowcoder.com