逮捕罪犯（树）- 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);
}
}