题目描述

在一片草原上有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贪心。

花O(n)的时间枚举一个一定放的点，

然后感性思考，这个点显然放在接近度大于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;

}