给你一个边权为 的无向图,动态加边,每次加边询问无向图的直径(所有点对的最短路中的最大值)。要求你的答案在真实答案的 倍之间(向上取整)。
。
有一个结论: 到其它点的最短路的最大值 和直径 一定满足 。
证明
显然, 则是因为要先走到直径上,再走到直径的两个端点。
所以初始答案 可以一直用到 ,那么二分出第一次减半的位置即可。
时间复杂度 。
代码如下:
// Problem: Approximate Diameter
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1804F
// Memory Limit: 500 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int S=100005;
struct node
{
int x,y;
}ed1[S],ed2[S];
int n,m,q;
vector<int> g[S];
int dis[S],ans[S];
inline int calc(int id)
{
for(int i=1;i<=id;i++) g[ed2[i].x].push_back(ed2[i].y),g[ed2[i].y].push_back(ed2[i].x);
for(int i=1;i<=n;i++) dis[i]=1e8;
queue<int> q;
q.push(1);
dis[1]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int v:g[u])
{
if(dis[u]+1<dis[v])
{
dis[v]=dis[u]+1;
q.push(v);
}
}
}
int mx=0;
for(int i=1;i<=n;i++) mx=max(mx,dis[i]);
for(int i=1;i<=id;i++) g[ed2[i].x].pop_back(),g[ed2[i].y].pop_back();
return mx;
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
ed1[i]=(node){x,y};
}
for(int i=1;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
ed2[i]=(node){x,y};
}
for(int i=1;i<=m;i++) g[ed1[i].x].push_back(ed1[i].y),g[ed1[i].y].push_back(ed1[i].x);
for(int i=0;i<=q;i++) ans[i]=-1;
for(int i=0;i<=q;i++)
{
ans[i]=calc(i);
int lb=i,rb=q,res=q;
while(lb<=rb)
{
int mid=lb+rb>>1;
if(calc(mid)*2>=ans[i]) res=mid,lb=mid+1;
else rb=mid-1;
}
i=res;
}
for(int i=1;i<=q;i++) if(ans[i]==-1) ans[i]=ans[i-1];
for(int i=0;i<=q;i++) printf("%d ",ans[i]);
printf("\n");
return 0;
}