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