【藍橋杯 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 博客，并完稿發布。