2020-08-18

http://icpc.upc.edu.cn/problem.php?cid=2548&pid=4

题目描述

在一片栖息地上有N棵树，每棵树下住着一只兔子，有M条路径连接这些树。更特殊地是，只有一棵树有3条或更多的路径与它相连，其它的树只有1条或2条路径与其相连。换句话讲，这些树和树之间的路径构成一张N个点、M条边的无向连通图，而度数大于2的点至多有1个。
近年以来，栖息地频繁收到人类的侵扰。兔子们联合起来召开了一场会议，决定在其中K棵树上建造树洞。当危险来临时，每只兔子均会同时前往距离它最近的树洞躲避，路程中花费的时间在数值上等于距离。为了在最短的时间内让所有兔子脱离危险，请你安排一种建造树洞的方式，使最后一只到达树洞的兔子所花费的时间尽量少。

输入

第一行有3个整数N，M，K，分别表示树（兔子）的个数、路径数、计划建造的树洞数。
接下来M行每行三个整数x,y，表示第x棵树和第y棵树之间有一条路径相连。1<=x,y<=N，x≠y，任意两棵树之间至多只有1条路径。

输出

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

样例输入

5 5 2
1 2
2 3
3 1
1 4
4 5

样例输出

1

提示

对于20%的数据，1 ≤  n ≤ 10。
对于另外30%的数据，每棵树至多与2条路径相连。
对于另外30%的数据，保证存在一种最优解，使与3条或更多路径相连的树上一定建造了树洞。
对于100%的数据，1 ≤ n ≤ 2000，n-1<=m<=n*(n-1)/2。

解析

图论+二分查找
注：本题缺乏测试用例，可能会有bug，建议参照博客：
https://www.cnblogs.com/Shawn7xc/p/7771441.html
https://www.cnblogs.com/candy99/p/6003565.html

#include
using namespace std;
typedef long long ll;
struct node
{
    int to;
    int next;
};
int n,m,x,y,k;
int head[100500]={0};
int vis[100500]={0};
int first[100500]={0};
int e[100500]={0};
node a[100500]={0};
int root=0;
int cnt=0;
int deep=0;
int dfs(int n,int len)
{
    deep+=1;
    vis[n]=1;
    if(len==0)
        return 0;
    for(int i=head[n];i;i=a[i].next)
    {
        int w=a[i].to;
        if(!vis[w])
        {
            dfs(w,len-1);
        }
    }
}
int add(int x,int y)
{
    a[++cnt].to=y;
    a[cnt].next=head[x];
    head[x]=cnt;
}
int check(int x)
{
    memset(vis,0,sizeof(vis));
    dfs(root,x);
    memcpy(first,vis,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        if(first[i])
        {
            int out=1;
            memset(vis,0,sizeof(vis));
            dfs(i,x);
            for(int j=1;j<=n;j++)
            {
                if(!vis[j])
                {
                    deep=0;
                    dfs(j,n);
                    out+=(deep+2*x)/(2*x+1);
                }
            }
            if(out<=k)
                return 1;
        }
    }
    return 0;
}
int main()
{
    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);
        e[x]++;
        e[y]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(e[i]>2)
        {
            root=i;
            break;
        }
    }
    if(!root)
    {
        cout<<(n+k-1)/k/2<<endl;
        exit(0);
    }
    int l=1,r=n+1;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            l=mid+1;
        }
        else
        {
            r=mid;
        }
    }
    cout<<l<<endl;
    return 0;
}