cfgym100519H

201707

• 现场时只想到二分，其他想法很乱。
• 因为中点一定要被覆盖，所以枚举能覆盖中点的所有点
• 那么当前这个点把图切成了很多链。dfs求点的个数，一个点能覆盖2*mid个点，对链计算一下即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(x) (int)x.size()
#define de(x) cout<< #x<<" = "<<x<<endl
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//------
const int N=1005;
bool tag[N],vis[N];
int n,m,k,o,siz;
int deg[N],dis[N];
vector<int> G[N];
void dfs(int u) {
    if(vis[u]) return ;
    vis[u]=1;++siz;
    rep(i,0,sz(G[u])) dfs(G[u][i]);
}
int calc(int u,int mid) {
    memset(vis,0,sizeof(vis));
    int res=1;
    vector<int> q;
    q.pb(u);dis[u]=mid;vis[u]=1;
    rep(_,0,sz(q)) {
        int u=q[_];
        if(dis[u]==0) continue;
        rep(i,0,sz(G[u])) {
            int v=G[u][i];
            if(vis[v]) continue;
            dis[v]=dis[u]-1;
            vis[v]=1;
            q.pb(v);
        }
    }
    rep(i,1,n+1) {
        if(!vis[i]) {
            siz=0;dfs(i);
            res+=siz/(2*mid+1);
            if(siz%(2*mid+1)) ++res;
        }
    }
    return res;
}
bool check(int mid) {
    memset(tag,0,sizeof(tag));
    vector<int> q;
    q.pb(o);dis[o]=mid;tag[o]=1;
    rep(_,0,sz(q)) {
        int u=q[_];
        if(dis[u]==0) continue;
        rep(i,0,sz(G[u])) {
            int v=G[u][i];
            if(tag[v]) continue;
            dis[v]=dis[u]-1;
            tag[v]=1;
            q.pb(v);
        }
    }
    rep(i,1,n+1) {
        if(tag[i]&&calc(i,mid)<=k) return 1;
    }
    return 0;
}
int main(){
    ///
    scanf("%d%d%d",&n,&m,&k);
    ///read
    rep(i,0,m) {
        int u,v;scanf("%d%d",&u,&v);
        ++deg[u];++deg[v];
        G[u].pb(v);
        G[v].pb(u);
    }
    ///
    if(k>=n) {
        puts("0");
        return 0;
    }
    ///get o
    o=-1;int t=1;
    rep(i,1,n+1) {
        if(deg[i]>2) o=i;
        if(deg[i]==1) t=i;
    }
    if(o==-1) o=t;
    ///solve
    int l=1,r=n,ans=-1;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(check(mid)) {
            ans=mid;
            r=mid-1;
        } else l=mid+1;
    }
    ///print
    printf("%d\n",ans);
    return 0;
}