题目
在一片草原上有 (N) 个兔子窝，每个窝里住着一只兔子，有M条路径连接这些窝。更特殊地是，至多只有一个兔子窝有3条或更多的路径与它相连，其它的兔子窝只有1条或2条路径与其相连。换句话讲，这些兔子窝之前的路径构成一张 (N) 个点、(M) 条边的无向连通图，而度数大于2的点至多有1个。
兔子们决定把其中 (K) 个兔子窝扩建成临时避难所。当危险来临时，每只兔子均会同时前往距离它最近的避难所躲避，路程中花费的时间在数值上等于经过的路径条数。为了在最短的时间内让所有兔子脱离危险，请你安排一种建造避难所的方式，使最后一只到达避难所的兔子所花费的时间尽量少。
分析
显然二分答案，然后判断能不能成功
首先考虑一条链，它需要的最少的避难所数量是 (lceil frac{len}{2 imes mid + 1}
ceil)
就是能不放就不放
环呢？
然后发现只有一个度数大于 (2) 的点
记为 (rt)
它必然是环上的点
如果把它删了，就只剩下一堆链
于是我们枚举一个可以覆盖 (rt) 的，把这个点能覆盖的所有点都删了
图只剩下一堆链
再统计每条链的长度 (len)，用上面的贪心办法算
算完后如果结果小于等于 (k)，那就成功了
于是就是 (O(N^2 log N)) 的
(Code)
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 1005 , M = 1505;
int n , m , k , tot , rt , h[N] , vis[N] , deg[N] , X[N];
struct edge{
int to , nxt;
}e[M * 2];
inline void add(int x , int y){e[++tot] = edge{y , h[x]} , h[x] = tot;}
void choose(int x , int d , int mid)
{
if (d <= mid) X[++X[0]] = x;
else return;
vis[x] = 1;
for(register int i = h[x]; i; i = e[i].nxt)
{
int v = e[i].to;
if (!vis[v]) choose(v , d + 1 , mid);
}
}
void del(int x , int d , int mid)
{
if (d > mid) return;
vis[x] = 1;
for(register int i = h[x]; i; i = e[i].nxt)
{
int v = e[i].to;
if (!vis[v]) del(v , d + 1 , mid);
}
}
int Get(int x)
{
int res = 1; vis[x] = 1;
for(register int i = h[x]; i; i = e[i].nxt)
{
int v = e[i].to;
if (!vis[v]) res += Get(v);
}
return res;
}
int check(int mid)
{
if (rt == 0) return (int)ceil(1.0 * n / (2 * mid + 1));
memset(vis , 0 , sizeof vis);
int num = 0; X[0] = 0 , choose(rt , 0 , mid);
for(register int i = 1; i <= X[0]; i++)
{
memset(vis , 0 , sizeof vis);
del(X[i] , 0 , mid) , num = 1;
for(register int i = 1; i <= n; i++)
if (!vis[i]) num += (int)ceil(1.0 * Get(i) / (2 * mid + 1));
if (num <= k) return 1;
}
return 0;
}
int main()
{
freopen("rabbit.in" , "r" , stdin);
freopen("rabbit.out" , "w" , stdout);
scanf("%d%d%d" , &n ,&m , &k);
int x , y;
for(register int i = 1; i <= m; i++)
scanf("%d%d" , &x , &y) , add(x , y) , add(y , x) , deg[x]++ , deg[y]++;
for(register int i = 1; i <= n; i++)
if (deg[i] >= 3){rt = i; break;}
if (n == 1){printf("0"); return 0;}
int l = 1 , r = n , mid , res;
while (l <= r)
{
mid = (l + r) >> 1;
if (check(mid)) res = mid , r = mid - 1;
else l = mid + 1;
}
printf("%d" , res);
}