CF1648E Air Reform 做题记录

一张 $n$ 个点 $m$ 条边的无向带权简单连通图，其上一条路径的权值为其中所有边权的 $\max$ 。

考虑这张图的补图，补图中一条边的权值为原图中该边两端点间的最短路（路径长度的定义同上）。保证补图亦是连通图。

对于原图中每条边，求出其两端点在补图中的最短路（定义仍同上）。

$1\le n,m\le 2\times 10^5$ ，边权范围 $[0,10^9]$ 。

下文所有最短路的定义都与题目中一致。

建出 kruskal 重构树，那么两点间的最短路就是它们 lca 的权值，而 lca 越深权值越小，所以在重构树的 dfn 序中到 $u$ 的最短路最小的点一定是 $u$ 左边离它最近的点或 $u$ 右边离它最近的点。

考虑找出补图的最小生成树，易证明两点在补图中的最短路等与它们在补图的最小生成树中的最短路。

发现补图是个稠密图，所以考虑 Boruvka 算法。

考虑怎么找到补图中距离某个连通块最近的点，可以转化为求出补图中到每个点最近的点。考虑给 $n$ 个点按照 dfs 序排序，那么相当于找到 $u$ 左边和右边最近的不在 $u$ 的连通块且在原图中与 $u$ 没有直接连边的点。这个可以考虑预处理同一个连通块的连续段，对于点 $u$ ，直接暴力往左往右依次找，遇到连续的与 $u$ 在同一个连通块的点就直接快速跳，遇到和 $u$ 有直接连边的点就跳过。

这样做的话 Boruvka 一轮时间复杂度是 $O(m)$ ，那么总时间复杂度为 $O(m\log n)$ 。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

// fastI
template<typename T>
inline void read(T &x)
{
	x=0;
	bool fl=false;
	char c=getchar();
	while(c<'0'||c>'9') fl^=c=='-',c=getchar();
	while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
	x=fl?-x:x;
}
template<>inline void read<char>(char &x)
{
	x=getchar();
	while(x==' '||x=='\r'||x=='\n') x=getchar();
}
inline void read(){return;};
template<typename T,typename ...Args>
inline void read(T &x,Args&...args){read(x),read(args...);}

// fastO
template<typename T>
void write(T x){x>9?write(x/10),putchar(x%10|48):putchar(x%10|48);}
template<>inline void write<char>(char x){putchar(x);}
template<typename T,typename ...Args>
inline void write(T x,Args...args){write(x),write(args...);}

const int S=200005,TS=400005,BS=25;

struct node
{
	int x,y,w,id;
}ed[S],ed2[S];

int n,m;
int fa[TS];
int cnt,b[TS];
vector<int> son[TS];
int fat[TS],dep[TS],tot,dfn[TS],a[TS],mlog[TS],mn[TS][BS];
vector<int> vc[S];
int pp[S];
int lb[S],rb[S],el[S],er[S],nxt[S],lst[S];
int mnl[S],mnr[S],mnlu[S],mnru[S],mnlv[S],mnrv[S];
int m2;

int fnd(int x)
{
	return fa[x]==x?x:fa[x]=fnd(fa[x]);
}

void dfs(int u,int fa)
{
	fat[u]=fa;
	dep[u]=dep[fa]+1;
	a[dfn[u]=++tot]=u;
	for(int v:son[u]) dfs(v,u);
}

inline void initlca()
{
	mlog[0]=-1;
	for(int i=1;i<=tot;i++) mlog[i]=mlog[i>>1]+1,mn[i][0]=i;
	for(int j=1;j<=mlog[tot];j++)
	{
		for(int i=1;i<=tot-(1<<j)+1;i++)
		{
			int x=mn[i][j-1],y=mn[i+(1<<j-1)][j-1];
			mn[i][j]=dep[a[x]]<dep[a[y]]?x:y;
		}
	}
}

inline int quelca(int x,int y)
{
	if(x==y) return x;
	x=dfn[x],y=dfn[y];
	if(x>y) swap(x,y);
	x++;
	int k=mlog[y-x+1];
	int aa=mn[x][k],bb=mn[y-(1<<k)+1][k];
	if(dep[a[aa]]<dep[a[bb]]) return fat[a[aa]];
	else return fat[a[bb]];
}

inline void kruskal(node *ed,int m)
{
	for(int i=1;i<=n*2;i++) son[i].clear();
	sort(ed+1,ed+m+1,[&](node x,node y){return x.w<y.w;});
	for(int i=1;i<=n*2;i++) fa[i]=i;
	cnt=n;
	for(int i=1;i<=n;i++) b[i]=0;
	for(int i=1;i<=m;i++)
	{
		int x=ed[i].x,y=ed[i].y;
		int rx=fnd(x),ry=fnd(y);
		if(rx==ry) continue;
		fa[rx]=fa[ry]=++cnt;
		son[cnt].push_back(rx),son[cnt].push_back(ry);
		b[cnt]=ed[i].w;
	}
	tot=0;
	dfs(cnt,0);
	initlca();
}

inline void boruvka()
{
	for(int i=1;i<=n;i++) vc[i].clear();
	for(int i=1;i<=n;i++) pp[i]=i;
	sort(pp+1,pp+n+1,[&](int x,int y){return dfn[x]<dfn[y];});
	for(int i=1;i<=m;i++) vc[ed[i].x].push_back(ed[i].y),vc[ed[i].y].push_back(ed[i].x);
	for(int i=1;i<=n;i++) sort(vc[i].begin(),vc[i].end(),[&](int x,int y){return dfn[x]<dfn[y];});
	m2=0;
	for(int i=1;i<=n;i++) fa[i]=i;
	while(1)
	{
		for(int i=1;i<=n;i++)
		{
			int j=i;
			while(j<n&&fnd(pp[j+1])==fnd(pp[i])) j++;
			for(int k=i;k<=j;k++) lb[pp[k]]=i-1,rb[pp[k]]=j+1;
			nxt[i]=j,lst[j]=i;
			i=j;
		}
		if(nxt[1]==n) break;
		for(int i=1;i<=n;i++)
		{
			el[i]=vc[i].size()-1;
			for(int j=0;j<vc[i].size();j++)
			{
				if(dfn[vc[i][j]]>dfn[pp[lb[i]]])
				{
					el[i]=j-1;
					break;
				}
			}
			er[i]=0;
			for(int j=vc[i].size()-1;j>=0;j--)
			{
				if(dfn[vc[i][j]]<dfn[pp[rb[i]]])
				{
					er[i]=j+1;
					break;
				}
			}
		}
		for(int i=1;i<=n;i++) mnlv[i]=mnrv[i]=2e9;
		for(int i=1;i<=n;i++)
		{
			int x=pp[i];
			while(lb[x]>=1&&(el[x]>=0&&vc[x][el[x]]==pp[lb[x]]))
			{
				lb[x]--,el[x]--;
				if(lb[x]>=1&&fnd(pp[lb[x]])==fnd(x)) lb[x]=lst[lb[x]]-1;
				while(el[x]>0&&dfn[vc[x][el[x]-1]]>=dfn[pp[lb[x]]]) el[x]--;
			}
			if(lb[x]>=1&&b[quelca(pp[lb[x]],x)]<mnlv[fnd(x)])
			{
				mnl[fnd(x)]=pp[lb[x]];
				mnlu[fnd(x)]=x;
				mnlv[fnd(x)]=b[quelca(pp[lb[x]],x)];
			}
			while(rb[x]<=n&&(er[x]<=vc[x].size()-1&&vc[x][er[x]]==pp[rb[x]]))
			{
				rb[x]++,er[x]++;
				if(rb[x]<=n&&fnd(pp[rb[x]])==fnd(x)) rb[x]=nxt[rb[x]]+1;
				while(er[x]<vc[x].size()-1&&dfn[vc[x][er[x]+1]]<=dfn[pp[rb[x]]]) er[x]++;
			}
			if(rb[x]<=n&&b[quelca(pp[rb[x]],x)]<mnrv[fnd(x)])
			{
				mnr[fnd(x)]=pp[rb[x]];
				mnru[fnd(x)]=x;
				mnrv[fnd(x)]=b[quelca(pp[rb[x]],x)];
			}
		}
		for(int i=1;i<=n;i++)
		{
			if(fa[i]==i)
			{
				if(mnlv[i]<mnrv[i])
				{
					int p=mnl[i];
					if(fnd(p)!=i)
					{
						ed2[++m2]={p,mnlu[i],mnlv[i],0};
						fa[fnd(p)]=i;
					}
				}
				else
				{
					int p=mnr[i];
					if(fnd(p)!=i)
					{
						ed2[++m2]={p,mnru[i],mnrv[i],0};
						fa[fnd(p)]=i;
					}
				}
			}
		}
	}
}

inline void slove()
{
	read(n,m);
	for(int i=1;i<=m;i++) read(ed[i].x,ed[i].y,ed[i].w),ed[i].id=i;
	kruskal(ed,m);
	boruvka();
	kruskal(ed2,m2);
	sort(ed+1,ed+m+1,[&](node x,node y){return x.id<y.id;});
	for(int i=1;i<=m;i++) write(b[quelca(ed[i].x,ed[i].y)],' ');
	write('\n');
}

int main()
{
	int T;
	read(T);
	while(T-->0) slove();
	return 0;
}

CF1648E Air Reform 做题记录

感谢您的支持，我会继续努力的!