CF1804F Approximate Diameter 做题记录

给你一个边权为 $1$ 的无向图，动态加边，每次加边询问无向图的直径（所有点对的最短路中的最大值）。要求你的答案在真实答案的 $\frac{1}{2}\sim 2$ 倍之间（向上取整）。

$1\le n,m,q\le 10^5$。

有一个结论：$1$ 到其它点的最短路的最大值 $dis$ 和直径 $d$ 一定满足 $\lceil\frac{d}{2}\rceil\le dis\le d$。

所以初始答案 $ans0$ 可以一直用到 $dis<\left\lceil\frac{ans0}{2}\right\rceil$，那么二分出第一次减半的位置即可。

时间复杂度 $O(n\log^2 n)$。

代码如下：

// 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;
}