ARC 029-C 高橋君と国家

ARC029C_Kruskal.cpp

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
#define int long long
 
struct Edge{
 
   int a, b, c;
 
   bool operator<(const Edge& hoge)const{
      return c<hoge.c;
   }
};

vector<int> parent; 
struct UnionFind{
 
   UnionFind(int n){
      for(int i=0; i<n; i++) parent.push_back(i);
   }
 
   int find(int x){
      if(parent[x]==x) return parent[x];
      else return parent[x]=find(parent[x]);
   }
 
   void unite(int x, int y){
      x=find(x);
      y=find(y);
      parent[y]=x;
   }
 
   bool same(int x, int y){
      return find(x)==find(y);
   }
};
 
signed main(){
 
   int N, M;
   cin>> N>> M;
   vector<Edge> g;
   for(int i=0; i<N; i++){
      int c;
      cin>> c;
      g.push_back(Edge{i, N, c});
   }
   for(int i=0; i<M; i++){
      int a, b, c;
      cin>> a>> b>> c;
      a--; b--;
      g.push_back(Edge{a, b, c});
   }
 
   sort(g.begin(), g.end());
 
   UnionFind uf(N+1);
   int c=0;
   for(auto e: g){
      int a=e.a, b=e.b;
      if(uf.same(a, b)) continue;
      uf.unite(a, b);
      c+=e.c;
   }
 
   cout<< c<< endl;
 
   return 0;
}