树洞（贪心）

Description

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

近年以来，栖息地频繁收到人类的侵扰。兔子们联合起来召开了一场会议，决定在其中K棵树上建造树洞。当危险来临时，每只兔子均会同时前往距离它最近的树洞躲避，路程中花费的时间在数值上等于距离。为了在最短的时间内让所有兔子脱离危险，请你安排一种建造树洞的方式，使最后一只到达树洞的兔子所花费的时间尽量少。

1 ≤ n ≤ 2000，n-1<=m<=n*(n-1)/2。

Input Format

第一行有3个整数N，M，K，分别表示树（兔子）的个数、路径数、计划建造的树洞数。

接下来M行每行三个整数x,y，表示第x棵树和第y棵树之间有一条路径相连。1<=x,y<=N，x≠y，任意两棵树之间至多只有1条路径。

Output Format

一个整数，表示在最优方案下，最后一只到达树洞的兔子所花费的时间。

Solution

这题算贪心吧，显然二分答案

枚举建树洞能覆盖特殊点（即度数>=3的点）的点，

在图中标记能够在时间内到达该点的所有点。

剩余若干条独立的链，直接求最少需要的树洞，判断即可

Code

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define N 2010
#define M 2000010
using namespace std;

struct info{
	int to,nex;
}e[M*2];
int n,m,k,tot,head[M*2],in[N],root;
int Ans,mid,len;

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-')f = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
	return x * f;
}

inline void add_edge(int u,int v){
	e[++tot].to=v;
	e[tot].nex=head[u];
	head[u]=tot;
}

struct node{int id,s;};
bool vis[N];
void bfs(int st){
	queue<node> q;
	q.push((node){st,0});
	memset(vis,0,sizeof(vis));
	vis[st]=1;
	
	while(!q.empty()){
		node u=q.front();q.pop();
		if(u.s==mid) continue;
		for(int i=head[u.id];i;i=e[i].nex){
			int v=e[i].to;
			if(vis[v]) continue;
			vis[v]=1;
			q.push((node){v,u.s+1});
		}
	}
}

void dfs(int u){
	len++;vis[u]=1;
	for(int i=head[u];i;i=e[i].nex){
		int v=e[i].to;
		if(vis[v]) continue;
		dfs(v);
	}
}

bool check(){
	for(int i=1;i<=n;++i){
		bfs(i);
		if(!vis[root]) continue;
		int sum=1;
		
		for(int u=1;u<=n;++u) if(!vis[u]) {
			len=0;
			dfs(u);
			sum+=(len-1)/((mid<<1)+1)+1;
		}
		if(sum<=k) return 1;
	}
	return 0;
}

int main() {
	n=read(),m=read(),k=read();
	if(k>=n){
		printf("0
");
		return 0;
	}
	for(int i=1;i<=m;++i){
		int u=read(),v=read();
		in[u]++,in[v]++;
		add_edge(u,v);
		add_edge(v,u);
	}
	
	root=0;
	for(int i=1;i<=n;++i)
		if(in[i]>=3) {root=i;break;}
	if(root==0){
		printf("%d
",((n-1)/k+1)>>1);
		return 0;
	}		
	int l=1,r=m;
	while(l<=r){
		mid=(l+r)>>1;
		if(check())
			Ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d
",Ans);
	return 0;
}