CF1804F Approximate Diameter 题解

题目链接

点击打开链接

题目解法

很有意思的题，但不难

首先一个显然的结论是：算着边的加入，直径长度递减
第一眼看到误差范围是 2 倍，可以想到二分
可以观察到如果取答案为 \(\frac{n}{2}\) 可以覆盖到 \(\frac{n}{4}\)（上下取整不重要），那这样每次可以把值域范围缩小 4 倍，然后只要二分直径在这个范围内的操作区间即可

但现在有问题是无法求出一个图的直径
继续考虑估测
有一个结论是：图上任意一点到其他点的最远距离 \(\ge \frac{diameter}{2}\)
这不难证明，具体来说，在直径上的点显然是满足结论的，不在直径上的点需要先到直径上，才能到端点，显然也是满足结论的

然后就稍微变化一下上面的二分区间就可以做到 \(O(n\log^2n)\) 的复杂度

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=100100,M=100100;
int n,m,q,ans[M],dis[N];
pii E[M<<1];
queue<int> que;
vector<int> G[N];
void add_edge(int x,int y){ G[x].pb(y),G[y].pb(x);}
int get_dia(int opt){
    F(i,1,n) G[i].clear(),dis[i]=-1;
    F(i,1,m) add_edge(E[i].x,E[i].y);
    F(i,1,opt) add_edge(E[i+m].x,E[i+m].y);
    que.push(1),dis[1]=0;
    while(!que.empty()){
        int u=que.front();que.pop();
        for(int v:G[u]) if(dis[v]==-1) dis[v]=dis[u]+1,que.push(v);
    }
    int ret=0;
    F(i,1,n) chkmax(ret,dis[i]);return ret;
}
int main(){
    n=read(),m=read(),q=read();
    F(i,1,m) E[i]={read(),read()};
    F(i,1,q) E[i+m]={read(),read()};
    int x=get_dia(0),L=0;
    while(true){
        int lo=L-1,hi=q+1;
        while(lo<hi-1){
            int mid=(lo+hi)/2,dia=get_dia(mid);
            if(dia>=(x+1)/2) lo=mid;
            else hi=mid;
        }
        F(i,L,lo) ans[i]=x;
        L=lo+1;
        if(!x) break;
        x/=2;
    }
    F(i,0,q) printf("%d ",ans[i]);puts("");
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}