l3-005 垃圾箱分布 (30 分)

题目描述：

在一个 $n$ 个点 $m$ 条边的无向图中，有 $k$ 个垃圾箱，每个垃圾箱可以处理一定范围内的垃圾。现在需要在图中选择一些点作为垃圾箱的位置，使得每个点到离它最近的垃圾箱的距离不超过该垃圾箱的处理范围。请你输出最少需要选择多少个点作为垃圾箱的位置。

输入格式：

第一行三个整数 $n,m,k$，表示点数，边数和垃圾箱个数。

接下来 $m$ 行，每行两个整数 $a,b$，表示点 $a$ 和点 $b$ 之间有一条无向边。

输出格式：

一个整数，表示最少需要选择多少个点作为垃圾箱的位置。

数据范围：

$1≤n≤10^5$

$1≤m≤2×10^5$

$1≤k≤n$

输入样例：

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

输出样例：

2

解题思路：

二分答案+最短路

二分答案是指二分最小的半径，使得可以用 $k$ 个垃圾箱覆盖整个图。

对于每个半径，我们可以用最短路算法求出每个点到最近的垃圾箱的距离，如果有一个点到最近的垃圾箱的距离超过了该垃圾箱的处理范围，那么就说明该半径不行，需要增大半径，否则就可以减小半径。

最短路算法可以用 Dijkstra 算法或者 Floyd 算法，但是由于 Floyd 算法的时间复杂度为 $O(n^3)$，所以在本题中不适用，我们可以使用 Dijkstra 算法，时间复杂度为 $O(mlogn)$。

C++ 代码