Codeforce 1095 F. Make It Connected 解析(思維、MST)

今天我們來看看CF1095F
題目連結

題目
給你$n$個點，每個點$u$還有一個值$a[u]$，還有給你$m$條可能的邊。
任兩點$(u,v)$都可能可以用$a[u]+a[v]$這個權值來連接。
一開始圖上沒有邊，求最小的權值使得圖連通。

前言

思考方向還是不夠正確阿…

想法

首先知道我們想要構造MST，並且注意到:如果不考慮多出來的$m$條邊，那麼從權值最小的點連到所有其他點就是一種最好的構造。
那麼我們只要把這$n-1$條邊納入考慮一起造MST就好。

程式碼:

const int _n=2e5+10;  
int parent[_n], rank[_n];  
inline void dsinit(int n) {for (int i = 0; i < n; i++)parent[i] = i;memset(rank, 0, sizeof rank);}  
inline int dsfind(int e) {return parent[e] == e ? e : parent[e] = dsfind(parent[e]);}  
inline void dsunion(int s1, int s2) {if (rank[s1] < rank[s2])swap(s1, s2);parent[s2] = s1;if (rank[s1] == rank[s2]) rank[s1]++;}  
//以上是dsu模板  
struct E{  
  int f,t;ll w;  
  bool operator<(const E& rhs)const{return w<rhs.w;}  
};  
int t,n,m,s1,s2,id=0,x,y;  
ll a[_n],sum=0,w;  
vector<E> e;  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);  
  cin>>n>>m;rep(i,0,n)cin>>a[i]; rep(i,0,m){  
    cin>>x>>y>>w;x--,y--;e.pb({x,y,w});  
  }id=0;rep(i,1,n)if(a[i]<a[id])id=i;  
  rep(i,m,m+n)if(i-m!=id)e.pb({id,i-m,a[id]+a[i-m]});  
  sort(all(e)); dsinit(n);  
  sum=0;rep(i,0,m+n-1){  
    s1=dsfind(e[i].f),s2=dsfind(e[i].t);  
    if(s1!=s2)dsunion(s1,s2),sum+=e[i].w;  
  }cout<<sum<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission