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

题目

Description

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

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

Input

第一行有3个整数N，M，K，分别表示兔子窝的个数、路径数、计划建造的避难所数。

接下来M行每行三个整数x,y，表示第x个兔子窝和第y个兔子窝之间有一条路径相连。任意两个兔子窝之间至多只有1条路径。

Output

一个整数，表示最后一只到达避难所的兔子花费的最短时间。

Sample Input

5 5 2

1 2

2 3

1 4

1 5

4 5

Sample Output

1

Data Constraint

对于30%的数据，N≤15，K≤4；

对于60%的数据，N≤100；

对于100%的数据，1≤K≤N≤1,000，1≤M≤1,500

Hint

在第2个和第5个兔子窝建造避难所，这样其它兔子窝的兔子最多只需要经过1条路径就可以到达某个避难所。

题解

图应该长成这样

就是一堆链和一堆环，中间那个点就是度数大于等于3的点

题目要求最优答案，想到二分

\(O(n)\)枚举一个必选的点，然后二分答案

从这个必选的点去搜索

把全部和必选点的距离小于当前的答案\(mid\)的全部打上标记

这是所有环都变成链，求出链长除以\(2*mid+1\)向上取整

最后判断，更新\(l,r\)

Code

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

struct node

{

	int to,head,next;

}a[3001];

int n,m,k,x,y,tot,l,r,mid,ans,d[1001],dis[1001];

bool b[1001],bj[1001];

void add(int x,int y)

{

	a[++tot].to=y;

	a[tot].next=a[x].head;

	a[x].head=tot;

}

int dfs(int now,int fa)

{

	if (bj[now]) return -1;

	if (b[now]) return 0;

	int k=0;

	bj[now]=true;

	for (int i=a[now].head;i;i=a[i].next)

	{

		if (a[i].to==fa) continue;

		int x=dfs(a[i].to,now);

		k+=x+1;

	}

	return k;

}

bool judge(int one,int deep)

{

	int sum=0,h=0,t=1;

	memset(b,false,sizeof(b));

	b[one]=true;

	dis[one]=0;

	d[1]=one;

	while (h++<t)

		for (int i=a[d[h]].head;i;i=a[i].next)

			if (!b[a[i].to]&&dis[d[h]]<deep)

			{

				d[++t]=a[i].to;

				b[a[i].to]=true;

				dis[d[t]]=dis[d[h]]+1;

			}

	memset(bj,false,sizeof(bj));

	for (int i=1;i<=n;++i)

		if (!bj[i]&&!b[i])

		{

			int x=dfs(i,0);

			if (x==-1) return false;

			sum+=x/(2*deep+1);

			if (x%(2*deep+1)) ++sum;

		}

	return sum<k;

}

int main()

{

	freopen("rabbit.in","r",stdin);

	freopen("rabbit.out","w",stdout);

	scanf("%d%d%d",&n,&m,&k);

	for (int i=1;i<=m;++i)

	{

		scanf("%d%d",&x,&y);

		add(x,y);add(y,x);

	}

	ans=2147483647;

	for (int i=1;i<=n;++i)

	{

		l=0;r=m;

		while (l<=r)

		{

			mid=(l+r+1)>>1;

			if (judge(i,mid)) ans=min(ans,mid),r=mid-1;

			else l=mid+1;

		}

	}

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

	fclose(stdin);

	fclose(stdout);

	return 0;

}

JZOJ 【NOIP2016提高A组集训第16场11.15】兔子的相关教程结束。