CH Round #72树洞[二分答案 DFS&&BFS]

树洞 CH Round #72 - NOIP夏季划水赛

描述

在一片栖息地上有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条路径。

输出格式

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

样例输入

样例输出

数据范围与约定

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

一开始读错题

官方题解：

二分答案。
枚举距离特殊点最近的建造的树洞是哪一个，记为X。
在图中删除能够在二分的时间内到达该树洞X的所有点。
此时图变为若干条独立的链，直接求最少需要的树洞数。
在所有枚举的情况中取最小值，与K比较确定二分范围变化。

其实这就是一条链，只不过有一个点可能连出多条链或者连乘环

一条链的话，答案就是(n-t)/(2*t）上取整

很明显可以二分最大时间，也就是节点的最短距离

把特殊点设为root，枚举从能覆盖root的点中选一个建造树洞，

剩下的没vis的全成了链，每条链每2*mid+1必定放一个树洞

注意cnt要+1,一开始建了一个嘛

//

//  main.cpp

//  ch72c

//

//  Created by Candy on 26/10/2016.

//  Copyright © 2016 Candy. All rights reserved.

//

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,m,t,x,y;

struct edge{

    int v,ne;

}e[N<<];

int h[N],cnt=;

void ins(int u,int v){

    cnt++;

    e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;

    cnt++;

    e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;

}

int root=,de[N];

int d[N],q[N],head=,tail=;

void bfs(int s){

    memset(d,-,sizeof(d));

    head=;tail=;

    q[++tail]=s;

    d[s]=;

    while(head<=tail){

        int u=q[head++];

        for(int i=h[u];i;i=e[i].ne){

            int v=e[i].v;

            if(d[v]==-){

                d[v]=d[u]+;

                q[++tail]=v;

            }

        }

    }

}

int vis[N],len;

void dfs(int u){

    vis[u]=;len++;

    for(int i=h[u];i;i=e[i].ne){

        int v=e[i].v;

        if(vis[v]) continue;

        dfs(v);

    }

}

int solve(int dis){

    int ans=INF;

    for(int x=;x<=n;x++){

        bfs(x);

        int cnt=;

        if(d[root]>dis) continue;

        memset(vis,,sizeof(vis));

        for(int i=;i<=n;i++) if(d[i]<=dis) vis[i]=;

        for(int i=;i<=n;i++) if(!vis[i]){

            len=;

            dfs(i);

            cnt+=(len-)/(*dis+)+;

        }

        ans=min(ans,cnt+);//!!!cnt+1

    }

    return ans;

}

int main(int argc, const char * argv[]) {

    n=read();m=read();t=read();

    for(int i=;i<=m;i++){x=read();y=read();de[x]++;de[y]++;ins(x,y);}

    for(int i=;i<=n;i++) if(de[i]>) {root=i;break;}

    if(!root){

        printf("%d",(n-t-)/(*t)+);

        return ;

    }

    if(n==t){printf("");return ;}

    int l=,r=n,ans=INF;

    while(l<=r){

        int mid=(l+r)/;

        if(solve(mid)<=t) ans=min(ans,mid),r=mid-;

        else l=mid+;

    }

    printf("%d",ans);

    return ;

}

秒客网