[leetcode]2492. 两个城市间路径的最小分数(并查集 排序后建边)

题目链接

题意

给定一个$n$个点 $m$条边的无向图
每条边有边权

求1-n的路径中最小的边权是多少
每条路可以重复走

思路

把边按边权降序排序
用并查集维护连通性
遍历每条边 每次合并边的起点和终点
如果1和n联通 并且这条边在1和n的这个连通块中
就对ans取min

Code

#define pii pair<int,int>
#define ar2 array<int,2>
#define ar3 array<int,3>
#define ar4 array<int,4>
#define endl '\n'
void cmax(int &a,int b){a=max(a,b);};
void cmin(int &a,int b){a=min(a,b);};
const int N=1e5+10,MOD=1e9+7,INF=0x3f3f3f3f;const long long LINF=LLONG_MAX;const double eps=1e-6;
int a[N];class UnionFind{
private:vector<int>p,s;public:int cnt=0;UnionFind(int n): p(n+1),s(n+1,1){iota(p.begin(),p.end(),0);cnt=n;}int find(int x){if(p[x]!=x) p[x]=find(p[x]);return p[x];}void merge(int u,int v){int uu=find(u),vv=find(v);if(uu!=vv){if(s[uu]>s[vv]){p[vv]=uu;s[uu]+=s[vv];}else{p[uu]=vv;s[vv]+=s[uu];}cnt--;}}bool is_connected(int u,int v){return find(u)==find(v);}int size(int x){return s[x];}
};class Solution {
public:int minScore(int n, vector<vector<int>>& roads) {UnionFind uf(n);vector<ar3>edges;for(auto e:roads){int u=e[0],v=e[1],d=e[2];edges.push_back({d,u,v});}sort(edges.begin(),edges.end(),greater<ar3>());int ans=INF;for(auto [d,u,v]:edges){uf.merge(u,v);if(uf.is_connected(1,n)){if(uf.is_connected(1,u)){cmin(ans,d);}}}return ans;}
};