【蓝桥杯 2024 省 Python B】缴纳过路费

【蓝桥杯 2024 省 Python B】缴纳过路费

蓝桥杯专栏：2024 省 Python B
算法竞赛：图论，生成树，并查集，组合计数，kruskal 最小生成树，乘法原理
题目链接：洛谷 【蓝桥杯 2024 省 Python B】缴纳过路费

题目描述：
在繁华的商业王国中，$N$ 座城市被 $M$ 条商路巧妙地连接在一起，形成了一个错综复杂的无向图网络。每条商路是双向通行的，并且任意两座城市之间最多只有一条直接的商路。每条商路都有它的规则，其中最引人注目的就是穿过
商路，需要缴纳过路费。因此，商人们在选择商路时必须格外认真。
有一位名叫小蓝的商人，他对于商路的花费有着自己独到的见解。在小蓝眼中，一条路线包含一条或多条商路，但路线的成本并不是沿途累积的过路费总和，而是这条路线上最贵的那一次收费。这个标准简单而直接，让他能迅速评估出一条路线是否划算。
于是，他设立了一个目标，即找出所有城市对，这些城市之间的最低路线成本介于他心中预设的两个数 $L$ 和 $R$ 之间。他相信，这样的路线既不会太廉价，以至于路况糟糕；也不会过于昂贵，伤害他精打细算的荷包。
作为小蓝的助手，请你帮助小蓝统计出所有满足条件的城市对数量。

输入格式：
输入的第一行包含四个整数 $N,M,L,R$，表示有 $N$ 座城市和 $M$ 条双向通行的商路，以及小蓝心中预设的最高过路费的下限 $L$ 和上限 $R$。
接下来 $M$ 行，每行包含三个整数 $u,v,w$，表示城市 $u$ 和城市 $v$ 之间有一条双向通行的商路，过路费为 $w$。保证每对城市之间最多只有一条直接的商路。
输出格式：
输出一行包含一个整数，表示满足条件的城市对数量。

数据范围：
对于 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. kruskal 最小生成树
3. 乘法原理

题目大意

给出 $n$ 个结点和 $m$ 条带权边，一个结点代表一座城市，一条边表示两座城市间的直接路径（题目保证不会出现重边），并定义一条路线的成本为组成这条路线的边中的最大边权。给出 $l,r$ 并定义符合要求的城市对满足这两个城市之间路径成本最小的路径的成本要在区间 $[l,r]$ 之间，求出在所有城市中符合要求的城市对的个数。

题目不能保证图是连通的。

解题方法

$f_i$–查并集数组，$di{s}_i$–能够到达结点 $i$ 且最小成本路径的成本小于或等于当前边的边权的结点个数，$ans$–最终答案。

$find(x)$ 函数为查并集中查找集合头元素的函数。

1. 存边并按边权从小到大排序。
2. 数组初始化，$f_i=i,di{s}_i=1$。
3. 按最小生成树模版遍历每一条边，结点为 $u,v$，计算 $x=find(u),y=find(v)$，如果 $x\ne y$ 将结点 $x$ 并到结点 $y$ 上，再如果该边的边权属于 $[l,r]$，那么更新 $ans=ans+di{s}_x\times di{s}_y$，不论 $ans$ 是否更新，最后更新 $di{s}_y=di{s}_y+di{s}_x$。

AC Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10,M = 2e5+10;
int f[N],dis[N],ans;//f[]--查并集数组,dis[]--能够到达该结点且最小成本路径的成本小于当前边的边权的结点个数,ans--最终答案
struct node
{
	int x,y,z;
	bool operator<(const node &w)const
	{
		return z<w.z;//按边权排序(重载运算符)
	}
} G[M];
int find(int x)//查并集函数
{
	if (x==f[x]) return x;
	return f[x]=find(f[x]);
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);//关闭输入输出同步
	int n,m,l,r;
	cin>>n>>m>>l>>r;
	for (int i=0; i<m; i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		G[i]= {x,y,z};//存边
	}
	sort(G,G+m);//排序(按边权排序--从小到大)
	for (int i=1; i<=n; i++) f[i]=i,dis[i]=1;//数组初始化
	for (int i=0; i<m; i++)//最小生成树模版
	{
		int x=G[i].x,y=G[i].y,z=G[i].z;
		int d=find(x),e=find(y);
		if (d!=e)//要这条边
		{
			f[d]=e;//并到结点 e 上
			if (z>=l&&z<=r)
				ans+=dis[d]*dis[e];//计算以该边的边权为最小成本路径的路径成本的满足要求的城市对
			dis[e]+=dis[d];//加到结点 e 上
		}
	}
	cout<<ans;//输出答案
	return 0;
}

End

感谢观看，如有问题欢迎指出。

更新日志

1. 2025/8/30 开始书写本篇 CSDN 博客，并完稿发布。