P11005 [蓝桥杯 2024 省 Python B] 缴纳过路费

题目描述

在繁华的商业王国中，$N$ 座城市被 $M$ 条商路巧妙地连接在一起，形成了一个错综复杂的无向图网络。每条商路是双向通行的，并且任意两座城市之间最多只有一条直接的商路。每条商路都有它的规则，其中最引人注目的就是穿过
商路，需要缴纳过路费。因此，商人们在选择商路时必须格外认真。

有一位名叫小蓝的商人，他对于商路的花费有着自己独到的见解。在小蓝眼中，一条路线包含一条或多条商路，但路线的成本并不是沿途累积的过路费总和，而是这条路线上最贵的那一次收费。这个标准简单而直接，让他能迅速评估出一条路线是否划算。

于是，他设立了一个目标，即找出所有城市对，这些城市之间的最低路线成本介于他心中预设的两个数 $L$ 和 $R$ 之间。他相信，这样的路线既不会太廉价，以至于路况糟糕；也不会过于昂贵，伤害他精打细算的荷包。

作为小蓝的助手，请你帮助小蓝统计出所有满足条件的城市对数量。

输入格式

输入的第一行包含四个整数 $N,M,L,R$，表示有 $N$ 座城市和 $M$ 条双向通行的商路，以及小蓝心中预设的最高过路费的下限 $L$ 和上限 $R$。

接下来 $M$ 行，每行包含三个整数 $u,v,w$，表示城市 $u$ 和城市 $v$ 之间有一条双向通行的商路，过路费为 $w$。保证每对城市之间最多只有一条直接的商路。

输出格式

输出一行包含一个整数，表示满足条件的城市对数量。

输入输出样例 #1

输入 #1

5 5 1 2
1 2 2
1 3 5
1 4 1
2 4 5
2 5 4

输出 #1

3

说明/提示

对于 30% 的评测用例，$1\le N\le 10^3,1\le M\le \min (2\times 10^3,\frac{N\times (N-1)}{2}),1\le L\le R\le 10^5，1\le u,v\le N,u\ne v,1\le w\le 10^5$。

对于所有评测用例，$1\le N\le 10^5,1\le M\le \min (2\times 10^5,\frac{N\times (N-1)}{2}),1\le L\le R\le 10^9,1\le u,v\le N,u\ne v，1\le w\le 10^9$。

样例解释

在样例中，满足条件的城市对有 $(1,2),(1,4),(2,4)$。

C++实现

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

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容