给定 (n) 个点,每个点有点权,连结两个点花费的代价为两点的点权和。另外有 (m) 条特殊边,参数为 (x,y,z)。意为如果你选择这条边,就可以花费 (z) 的代价将点 (x) 和点 (y) 连结起来,当然你也可以不选择这条边。求使整个图联通的最小代价
Solution
模拟 Kruskal 过程,同时维护每个集合的最小点权,每次比较当前最小特殊边的边权和最小点权的两个集合的和,走比较小的那一个
用 std::set
维护即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
int n,m,a[N];
struct edge {
int u,v,w;
bool operator < (const edge &b) {
return w < b.w;
}
} e[N];
set<pair<int,int> > s;
int fa[N],mn[N],ans;
int find(int p) {
return fa[p]==p ? p : fa[p]=find(fa[p]);
}
void merge(int p,int q) {
p=find(p); q=find(q);
if(p-q) {
s.erase(s.find({mn[p],p}));
s.erase(s.find({mn[q],q}));
fa[q]=p, mn[p]=min(mn[p],mn[q]);
s.insert({mn[p],p});
}
}
int eval() {
auto i=s.begin();
auto j=i;
++j;
return i->first + j->first;
}
signed main() {
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
sort(e+1,e+m+1);
int pos=1;
for(int i=1;i<=n;i++) fa[i]=i, mn[i]=a[i];
for(int i=1;i<=n;i++) s.insert({mn[i],i});
while(s.size()>1) {
if(eval()<e[pos].w || pos>m) {
ans+=eval();
auto i=s.begin();
auto j=i;
++j;
merge(i->second,j->second);
}
else {
if(find(e[pos].u)!=find(e[pos].v)) {
merge(e[pos].u,e[pos].v);
ans+=e[pos].w;
}
++pos;
}
}
cout<<ans;
}