小红的图上加边时间限制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查找连通块并计算块内最大值小根堆贪心合并最小的两个值。效率保障线性处理图结构堆操作高效整体复杂度满足题目时间限制。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e510;constll p1e97;constll INF1e18;constll M2e310;ll a[N];vectorvectorllg(N);boolvis[N];priority_queuell,vectorll,greaterllpq;//大根堆voidbfs(ll x){ll mx-1;queuellq;q.push(x);while(!q.empty()){ll yq.front();mxmax(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;cinnm;for(ll i1;in;i)cina[i];for(ll i1;im;i){ll u,v;cinuv;g[u].push_back(v);g[v].push_back(u);}ll cnt0;//连通块的个数for(ll i1;in;i){if(!vis[i]){bfs(i);cnt;}}ll ans0;while(pq.size()1){ll upq.top();pq.pop();ll vpq.top();pq.pop();ansmax(u,v);pq.push(max(u,v));}coutansendl;return0;}