# 逮捕罪犯（树）- 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

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

```#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);
//添加来回路线
}
//深度优先搜索
int ans = dfs(1, 0);

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

212 篇文章32 人订阅

0 条评论

## 相关文章

3381

1672

3274

5756

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

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

3106

7711

### 如何掌握所有的编程语言

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

4968

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

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

3735

34910

3477