自动搬运

查看原文

来自洛谷，原作者为

	Albert_van 告♂诫之心 赞♂美之心 许♂容之心

搬运于2025-08-24 22:50:58，当前版本为作者最后更新于2023-11-07 20:22:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Boruvka 蓝莓算法模板题。

首先图的规模太大，考虑压缩一些点或状态。$m$ 条指定边只涉及 $2m$ 个结点，称它们为关键点，那么相邻关键点 $l$ 与 $r$ 间所有点的连边没有限制。于是在整个图的 MST 中，必然有一条长 $r-l-2$ 的链贯穿 $[l+1,r-1]$ 间所有非关键点。

要证明，考虑利用 MST 的性质：$x$ 到 $y$ 在树上路径最大值，等于原图路径最大值的最小值。这里对 $x,y\in(l,r)$ 有 $x$ 到 $y$ 路径最大值为 $1$。因为 $x$ 和 $y$ 连向外界的边权不会小于 $1$，所以连成链必然不劣。

于是先令答案加上 $r-l-2$，然后将 $[l+1,r-1]$ 串起来视作一个结点，与关键点一起加入图中。这样点数就降到了 $\mathcal O(m)$ 级别。

对这个新的完全图，使用蓝莓算法求 MST，每轮需对每个点求出离开连通块的最小边。对于指定的关键点间连边，逐个用边权更新两端点即可。考虑剩下边权为两点距离的连边。

初始每个点独立组成连通块时，可以从点 $i$ 出发暴力向前/后跳（$p\gets p\mp 1$），找到离 $i$ 最近的 $p$ 满足 $i$ 与 $p$ 间没有指定边。这个过程显然花费 $\mathcal O(m)$。

在一个连通块有多个点时，$p$ 必须同时满足 $p$ 与 $i$ 不在同一块内，复杂度无法保证。进行优化，记录 $\operatorname{pre}_p$ 表示 $p$ 之前第一个不在 $p$ 的连通块内的点，$\operatorname{nxt}_p$ 同理。那么遇到 $p$ 与 $i$ 在同一块内时，令 $p\gets \operatorname{pre}_p/\operatorname{nxt}_p$ 即可。每次这样的操作后，要么 $p$ 合法并结束，要么进行一次 $p\gets p\mp 1$ 的操作，所以这里的花费也是 $\mathcal O(m)$。

于是每一轮 $\mathcal O(m)$，总复杂度 $\mathcal O(m\log m)$。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>

using namespace std;

const int N=514114;

namespace U{
	int anc[N];
	void set(int n){for(int i=1;i<=n;++i) anc[i]=i;}
	int fnd(int x){return anc[x]==x?x:anc[x]=fnd(anc[x]);}
	void mrg(int x,int y){anc[fnd(x)]=fnd(y);}
}using namespace U;

struct point{int p,id;}pt[N];

struct ed{
	int v,w;
	bool operator<(const ed t)const{return v<t.v;}
};
vector<ed> vc[N];

bool ex(int x,int y){
	auto p=lower_bound(vc[x].begin(),vc[x].end(),(ed){y,0});
	return p!=vc[x].end()&&p->v==y;
}

struct edg{int x,y,w;}e[N];

void upe(edg &k,edg n){if(n.w<k.w) k=n;}

map<int,int> pos;

int u[N],v[N],we[N],l[N],r[N],pre[N],nxt[N];

int main()
{
	int T;scanf("%d",&T);while(T--){
		int n,m;scanf("%d%d",&n,&m);
		for(int i=1;i<=m;++i){
			scanf("%d%d%d",u+i,v+i,we+i);if(u[i]<v[i]) swap(u[i],v[i]);
			pt[i*2-1]=(point){u[i],i};pt[i*2]=(point){v[i],0};
		}
		sort(pt+1,pt+(m<<1|1),[](point x,point y){return x.p<y.p;});
		long long ans=0;int c=0;
		for(int i=1;i<=m<<1;++i){
			int pl=pt[i-1].p,pr=pt[i].p;
			if(pr>pl+1) ans+=pr-pl-2,++c,l[c]=pl+1,r[c]=pr-1;
			if(pr>pl) ++c,l[c]=r[c]=pr;
			pos[pr]=c;int x=pt[i].id;
			if(x) vc[c].push_back((ed){pos[v[x]],we[x]}),vc[pos[v[x]]].push_back((ed){c,we[x]});
		}
		if(pt[m<<1].p<n) ++c,l[c]=pt[m<<1].p+1,r[c]=n,ans+=n-l[c];
		set(n=c);for(int i=1;i<=n;++i) sort(vc[i].begin(),vc[i].end());
		nxt[n+1]=anc[n+1]=0;int kc=n;while(kc>1){
			for(int i=1;i<=n;++i) if(fnd(i)==i) e[i].w=1e9+7;
			for(int i=1;i<=n;++i) pre[i]=fnd(i)==fnd(i-1)?pre[i-1]:i-1;
			for(int i=n;i;--i) nxt[i]=fnd(i)==fnd(i+1)?nxt[i+1]:i+1;
			for(int i=1;i<=n;++i){
				int p=i,a=fnd(i);
				while(fnd(p)==a||ex(i,p)) p=fnd(p)==a?pre[p]:p-1;
				if(p) upe(e[a],(edg){i,p,l[i]-r[p]});
				p=i;while(fnd(p)==a||ex(i,p)) p=fnd(p)==a?nxt[p]:p+1;
				if(p<=n) upe(e[a],(edg){i,p,l[p]-r[i]});
			}
			for(int i=1;i<=n;++i) for(auto[v,w]:vc[i]) if(fnd(i)!=fnd(v))
				upe(e[fnd(i)],(edg){i,v,w});
			for(int i=1;i<=n;++i) if(fnd(i)==i&&fnd(e[i].x)!=fnd(e[i].y))
				U::mrg(e[i].x,e[i].y),ans+=e[i].w,--kc;
		}
		printf("%lld\n",ans);
		for(int i=1;i<=n;++i) vc[i].clear();
	}
}