小红的图上加边【牛客tracker 每日一题】
小红的图上加边
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小红有一张n nn个点m mm条边的无向图，每个节点的权值是a i a_iai。
现在小红希望加边把这个图连成连通图，每次连接的代价是新形成的联通块的最大元素值，小红想知道最小需要消耗多少代价可以把这个图连成连通的。
输入描述：
第一行输入两个整数n nn和m ( 1 ≤ n ≤ 10 5 ; 0 ≤ m ≤ 10 5 ) m( 1≤n≤10^5;0≤m≤10^5)m(1≤n≤105;0≤m≤105)表示点数和边数。
第二行输入n nn个整数a 1 , a 2 , … , a n ( 1 ≤ a i ≤ 10 9 ) a_1,a_2,…,a_n (1≤a_i≤10^9)a1,a2,…,an(1≤ai≤109)表示每个节点的权值。
接下来m mm行，第i ii行输入两个整数u i u_iui 和v i ( 1 ≤ u i , v i ≤ n ) v_i (1≤u_i,v_i≤n)vi(1≤ui,vi≤n)表示无向图上第i ii条边连接节点u i u_iui 和v i v_ivi，保证没有重边。
输出描述：
在一行上输出一个整数，表示最小需要消耗的代价。
示例1
输入：
5 3 1 2 3 4 5 1 2 2 3 1 3输出：
9说明：
先加上( 1 , 4 ) (1,4)(1,4)这条边，代价是4 44，然后加上( 1 , 5 ) (1,5)(1,5)这条边，代价是5 55，总代价是9 99。
解题思路
本题核心是连通块统计+哈夫曼贪心算法求解最小加边代价。首先通过B F S BFSBFS遍历无向图，找到所有连通分量，并计算每个连通块内节点的最大权值。将问题转化为：合并k个连通块为1 11个，每次合并两个块的代价为两者最大值，求最小总代价。采用小根堆贪心策略，每次取出堆中两个最小的连通块最大值，合并代价为二者最大值并累加答案，再将合并后的最大值放回堆，重复操作直至堆中仅剩一个元素。该方法B F S BFSBFS线性遍历图，堆操作复杂度为对数级，完美适配n,m≤1e5的大数据规模。
总结
核心逻辑：统计所有连通块的最大值，利用哈夫曼贪心算法合并，最小化总代价。
关键操作：B F S BFSBFS查找连通块并计算块内最大值，小根堆贪心合并最小的两个值。
效率保障：线性处理图结构，堆操作高效，整体复杂度满足题目时间限制。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vt;typedefpair<ll,ll>pll;constll N=1e5+10;constll p=1e9+7;constll INF=1e18;constll M=2e3+10;ll a[N];vector<vector<ll>>g(N);boolvis[N];priority_queue<ll,vector<ll>,greater<ll>>pq;//大根堆voidbfs(ll x){ll mx=-1;queue<ll>q;q.push(x);while(!q.empty()){ll y=q.front();mx=max(mx,a[y]);q.pop();if(vis[y])continue;vis[y]=1;for(autou:g[y]){if(vis[u])continue;q.push(u);}}pq.push(mx);}intmain(){ll n,m;cin>>n>>m;for(ll i=1;i<=n;i++)cin>>a[i];for(ll i=1;i<=m;i++){ll u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}ll cnt=0;//连通块的个数for(ll i=1;i<=n;i++){if(!vis[i]){bfs(i);cnt++;}}ll ans=0;while(pq.size()>1){ll u=pq.top();pq.pop();ll v=pq.top();pq.pop();ans+=max(u,v);pq.push(max(u,v));}cout<<ans<<endl;return0;}