自动搬运

查看原文

来自洛谷，原作者为

	KSCD_ 知不可乎骤得，知来者之可追. | Defection,Retribution,Testify. | Rotating_Catfood

搬运于2025-08-24 23:03:23，当前版本为作者最后更新于2024-09-24 10:38:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

给出一张 $n$ 个点 $m$ 条边的带权无向图。定义路径的权值为路径上所有边权的最大值，设 $f(u,v)$ 表示 $u,v$ 之间的所有路径中最小的路径权值，求满足 $u<v,l\le f(u,v)\le r$ 的二元组 $(u,v)$ 的数量。

思路

考虑转化条件，不难发现 $f(u,v)=x$ 等价于 $u,v$ 不能通过所有边权小于 $x$ 的边连通，而能通过所有边权不大于 $x$ 的边连通。

那么按照边权从小到大加入每一条边，当加入一条边权为 $x$ 的边时，由不连通转为连通的点对即为 $f(u,v)=x$ 的点对。也就是说若这条边连接了两个不同的连通块，大小分别为 $s_p,s_q$，那么这些点两两匹配后就有 $s_ps_q$ 个 $f(u,v)=x$ 的点对。

按边权排序后依次加边，用并查集维护连通块及大小，在 $l\le x\le r$ 时统计答案即可。

代码

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=2e5+10;
const int inf=2e18;
int n,m,l,r,res,f[N],s[N];
struct edg {int u,v,w;}e[N];
bool cmp(edg ta,edg tb) {return ta.w<tb.w;}
int finds(int x) {return (f[x]==x?x:f[x]=finds(f[x]));}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>l>>r,e[m+1].w=inf;
	for(int i=1;i<=n;i++) f[i]=i,s[i]=1;
	for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
	sort(e+1,e+1+m,cmp); int now=1;
	while(e[now].w<=r)
	{
		int fu=finds(e[now].u),fv=finds(e[now].v);
		if(fu!=fv)
		{
			if(e[now].w>=l) res+=s[fu]*s[fv];
			f[fu]=fv,s[fv]+=s[fu];	
		}
		now++;
	}
	cout<<res;
	return 0;
}