---
title: Codeforce 1095 F. Make It Connected 解析(思維、MST)
description: "Codeforce 1095 F. Make It Connected 解析(思維、MST)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 1095 F. Make It Connected 解析(思維、MST)">
<!-- toc -->

# Codeforce 1095 F. Make It Connected 解析(思維、MST)
今天我們來看看CF1095F
[題目連結](https://codeforces.com/problemset/problem/1095/F)

> **題目**
給你$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](https://codeforces.com/contest/1095/submission/90524150)