P11005 题解

KSCD_ · 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;
}