题目

在一片草原上有 \(N\) 个兔子窝，每个窝里住着一只兔子，有M条路径连接这些窝。更特殊地是，至多只有一个兔子窝有3条或更多的路径与它相连，其它的兔子窝只有1条或2条路径与其相连。换句话讲，这些兔子窝之前的路径构成一张 \(N\) 个点、\(M\) 条边的无向连通图，而度数大于2的点至多有1个。

兔子们决定把其中 \(K\) 个兔子窝扩建成临时避难所。当危险来临时，每只兔子均会同时前往距离它最近的避难所躲避，路程中花费的时间在数值上等于经过的路径条数。为了在最短的时间内让所有兔子脱离危险，请你安排一种建造避难所的方式，使最后一只到达避难所的兔子所花费的时间尽量少。

分析

显然二分答案，然后判断能不能成功

首先考虑一条链，它需要的最少的避难所数量是 \(\lceil \frac{len}{2 \times mid + 1} \rceil\)

就是能不放就不放

环呢？

然后发现只有一个度数大于 \(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);

}

巴特西

JZOJ 4896. 【NOIP2016提高A组集训第16场11.15】兔子

题目

分析

\(Code\)

最新文章

热门文章