题目描述
在一片草原上有N个兔子窝，每个窝里住着一只兔子，有M条路径连接这些窝。更特殊地是，至多只有一个兔子窝有3条或更多的路径与它相连，其它的兔子窝只有1条或2条路径与其相连。换句话讲，这些兔子窝之前的路径构成一张N个点、M条边的无向连通图，而度数大于2的点至多有1个。
兔子们决定把其中K个兔子窝扩建成临时避难所。当危险来临时，每只兔子均会同时前往距离它最近的避难所躲避，路程中花费的时间在数值上等于经过的路径条数。为了在最短的时间内让所有兔子脱离危险，请你安排一种建造避难所的方式，使最后一只到达避难所的兔子所花费的时间尽量少。
数据范围
对于30%的数据，N≤15，K≤4；
对于60%的数据，N≤100；
对于100%的数据，1≤K≤N≤1,000，1≤M≤1,500
=w=
SB贪心。
花
然后感性思考，这个点显然放在接近度大于3的那个点的附近，这样可以尽量覆盖更多的窝。
这时，所有环都将切割为一条链，所以现在的所有连通块都是链。
考虑二分答案，那么每条链的贡献都是确定的，为链长除以(2*mid+1)向上取整。
然后答案就易求。
代码
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define ll long long
using namespace std;
const char* fin="rabbit.in";
const char* fout="rabbit.out";
const int inf=0x7fffffff;
const int maxn=1007,maxm=1507*2;
int n,m,n1,i,j,k,ans,tmp,tmd;
int f[maxn][maxn];
int fi[maxn],la[maxm],ne[maxm],tot;
int l,r,mid,head,tail,b[maxn];
int dis[maxn];
bool bz[maxn],az[maxn];
void add_line(int a,int b){
tot++;
ne[tot]=fi[a];
la[tot]=b;
fi[a]=tot;
}
void add(int v,int v1,int limit){
if (!bz[v] && v1<=limit){
b[++tail]=v;
dis[v]=v1;
bz[v]=true;
}
}
int dfs(int v,int from){
int i=0,j,k;
if (az[v]) return -1;
if (bz[v]) return 0;
az[v]=true;
for (k=fi[v];k;k=ne[k])
if (la[k]!=from){
j=dfs(la[k],v);
if (j==-1) return -1;
i+=j+1;
}
return i;
}
bool judge(int st,int v){
int i,j,k,sum=0;
head=tail=0;
memset(bz,0,sizeof(bz));
add(st,0,v);
while (head++<tail) {
for (k=fi[b[head]];k;k=ne[k]) add(la[k],dis[b[head]]+1,v);
}
memset(az,0,sizeof(az));
for (i=1;i<=n;i++)
if (!az[i] && !bz[i]){
j=dfs(i,0);
if (j==-1) return false;
sum+=j/(2*v+1)+(j%(2*v+1)?1:0);
}
return sum+1<=n1;
}
int main(){
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
scanf("%d%d%d",&n,&m,&n1);
for (i=1;i<=m;i++){
scanf("%d%d",&j,&k);
add_line(j,k);
add_line(k,j);
}
ans=inf;
for (i=1;i<=n;i++){
l=0;
r=m;
while (l<r){
mid=(l+r)/2;
if (judge(i,mid)) r=mid;
else l=mid+1;
}
ans=min(ans,l);
}
cout<<ans<<endl;
return 0;
}