逮捕罪犯(树)- HDU 3069

Problem Description

Country ALPC has n cities, and the cities are connected by undirected roads. Furthermore, there is exactly one route between each pair of cities. Now some criminals break the prison and the police do not know where they are. And the criminals can stay in a city or move on the roads. The police office has made a decision to send policemen to arrest the breakers. If a police and a criminal at a same point at the same time the criminal is under arrest, no matter in a city or on a road. The police office wants to minimize the number of policemen to arrest all the criminals. Now the map of Country ALPC is given, please tell the police office the least number of policemen required.

(ALPC国家有n个城市,城市之间没有直接连接的道路,并且,每两个城市之间只有唯一的一条路,现在有一些罪犯越狱了,警察不知道他们逃到了哪里。罪犯可能呆在一个城市或者在路上行进。警察局决定派一些警察去逮捕越狱者。如果警察和逃犯同时在一个城市或者一条路上则能抓捕逃犯,现在准备派遣最少的警力来处理这件事情,给出了ALPC国家的地图,请告诉警署至少需要多少警力)

Input

There are several test cases.

The first line a integer n, the number of cities. Next n-1 lines each two integers a and b, there is a road between city a and city b.

(1<=n <= 1000, 1 <= a, b <= n)

(输入:有多个用例,第一行输入一个城市数量n,下面n-1行,每行的数据a-b表示a与b之间有一条路。)

Output

For each case output the minimal number of policemen.

(输出:每一个用例输出最少警力数)

Sample Input

3

1 2

2 3

16

1 2

1 3

1 4

5 6

5 7

10 8

8 11

9 12

9 13

14 1

14 15

15 16

15 8

9 16

14 5

Sample Output

1

3

题意解析:

用最少警力追捕逃犯,这道题在一开始比较难于理解的是题意比较抽象,不知道如何构造逻辑。可以画一个图对于如何抓捕罪犯,其实也就是让警察守住所有的点,然后像撒网一样不允许罪犯从一个点移动到另外一个点。

如果一个父节点存在2个子节点,那么必须一个警察守住这个父节点,另外一个警察去子节点抓人。

来看一张图:

关于树:

一个无根树是一个二元组(V,E),在离散数学中,无根树指无环连通无向图。

所谓的 无向图,就是一个图中若每条边都是没有方向的,则称为无向图。

无向图中的边,均是顶点的无序对,无序对通常用圆括号表示。

无根树要求每个顶点之间都是直接或者间接相连,且图中没有环(即只有简单路径)。因为不能有环,所以任意两个点之间,只有一条路径能走的通,假如有两条路径能走得通,就形成了一个环了。

由于树是图的子集,这一类图具有树的特征,但不具备数的形式,没有特定的根结点,故称为无根树。

(注:这说明,无根树和有根树几乎是一样的,除了有根树有根结点,而根结点又是指定的,即给一个无根树,然后指定一个结点为根,那么这个无根树就成为了有根树)

源代码:G++,数组实现

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

#define maxn 1005

int next_cities[maxn], current_id;

typedef struct edge_s
{
    int to, next;
}edge_t;

edge_t edges[maxn * 2];

//添加edge
void add_edge(int next, int to)
{
    //设置路线的到达的城市id
    edges[current_id].to = to;
    //设置路线从哪来的城市id,注意这里有点难以理解
    //其实是对于同一个城市a,可能去b/c/d等城市,这里是用一个链表来保存的
    //反向链表
    edges[current_id].next = next_cities[next];
    //查找表,指向数组edges的索引
    next_cities[next] = current_id++;
}

int dfs(int city_id, int prev_city)
{
    int max_police = -1, cnt = 0;

    vector<int> max_set;
    //对于城市u,遍历所有的下一个城市
    for (int i = next_cities[city_id]; i != -1; i = edges[i].next)
    {
        //获取该节点的下一个节点
        int to = edges[i].to;

        if (to == prev_city)
            continue;

        //计算最大警力数
        int temp = dfs(to, city_id);

        max_set.push_back(temp);
        //更新最大值
        max_police = max_police > temp ? max_police : temp;
    }

    //如果是叶子节点,直接返回
    if (max_set.size() == 0) 
        return 1;

    //如果存在多个最大值
    for (int i = 0; i < max_set.size(); i++) 
        if (max_set[i] == max_police) 
            cnt++;
    //则需要一个人把手在根部节点(相对的根部)
    if (cnt > 1) 
        return max_police + 1; 

    return max_police;
}

int main()
{
    //n个城市
    int n;
    int u, v;

    while (scanf("%d", &n) != EOF)
    {
        current_id = 0;
        memset(next_cities, -1, sizeof(next_cities));

        for (int i = 0; i < n - 1; i++)
        {
            scanf("%d%d", &u, &v);
            //添加来回路线
            add_edge(u, v);
            add_edge(v, u);
        }
        //深度优先搜索
        int ans = dfs(1, 0);

        printf("%d\n", ans);
    }
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-01-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员八阿哥

王老板Python面试(11):真实 Python 爬虫面试题

就在昨天我面试了,来到上海之后面试的第一家公司,面试过程挺顺利,不出意外今天下午就会收到 offer。面试完之后,我走在路上,整个人都是在傻笑的状态,路人一脸关...

3381
来自专栏Pythonista

day24,python习题

有两个列表,分别存放来老男孩报名学习linux和python课程的学生名字 linux=['钢弹','小壁虎','小虎比','alex','wupeiqi'...

1672
来自专栏HansBug's Lab

面向对象先导课感想

下来我将分点讲述下收获和感想以及相关意见和建议。 收获和感想 作为一个虽然没有专门学过java但是早已经熟悉OOP程序设计方式,并使用 C# 有过大概几千行开发...

3274
来自专栏前端说吧

JS-过滤敏感词【RegExp】

5756
来自专栏take time, save time

[细节决定B度]之二分搜索也不易啊

     实事求是的说二分搜索是我学习算法的时候学的最好,理解的最透彻,能够当时就写出代码的的算法。事到如今,就如我可以分分钟写出hello world一样,我...

3106
来自专栏诸葛青云的专栏

利用c语言制作简易计算器

学了c语言之后,总想着能用c语言能制作一些简单的小工具来。而利用c语言来制作一款简易的计算器是一个不错的选择,用这款计算器可以计算的加、减、乘、除。

7711
来自专栏程序员宝库

如何掌握所有的编程语言

100本前端书籍下载|前端全套视频下载 对的,我这里要讲的不是如何掌握一种编程语言,而是所有的。 本文作者王垠,代表作《完全用Linux 工作》,著名软件工...

4968
来自专栏Java学习网

优秀的程序员是懂指针和递归的

  上周还是什么时候,和老大的一次谈话,他提到,他觉得Java程序员只能是个半吊子(大概意思是这样)。当时,我反驳说,其实还是可以有牛人的。但元旦琢磨了下,觉得...

3735
来自专栏大数据钻研

由浅入深的前端面试题 和矫情的“浪漫主义”诗句

好吧,我承认太标题党了,这篇文章是通过一道前端面试题引出的纯技术讨论。我先要矫情无比的从中外诗歌说起。 传统的佛学经典里,被世人熟知的有这样一句话:“一花一世界...

34910
来自专栏程序人生

抽象的能力

人类的智商从低幼逐渐走向成熟的标志之一就是认识和运用数字的能力。当我们三四岁的时候,数数虽然能够熟练地对一百以内的数字随心所欲地倒背如流,但数字对孩童时代的我们...

3477

扫码关注云+社区

领取腾讯云代金券