SHARE
TWEET

Untitled

a guest Feb 14th, 2020 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,m;
  4. int parent[100001];
  5. int find(int u) {
  6.     if (parent[u] == u)
  7.         return u;
  8.     return parent[u] = find(parent[u]);
  9. }
  10. void merge(int u, int v) {
  11.     u = find(u), v = find(v);
  12.     if (u == v)
  13.         return ;
  14.     parent[u] = v;
  15. }
  16. struct Edge {
  17.     int u,v,w;
  18.     bool operator <(const Edge & rhs) const{
  19.         return w< rhs.w;
  20.     }
  21. };
  22. vector <Edge> edges;
  23. int main(){
  24.     scanf("%d",&n);
  25.     int weight[n+1];
  26.     for(int i=1;i<=n;i++){
  27.         scanf("%d ",&weight[i]);
  28.     }
  29.     scanf("%d",&m);
  30.     for(int i=1;i<=m;i++){
  31.         int u,v;
  32.         scanf("%d %d",&u,&v);
  33.         edges.push_back({u,v,weight[u]+weight[v]});
  34.         parent[u]=u;
  35.         parent[v]=v;
  36.     }
  37.     sort(edges.begin(),edges.end());
  38.     int sum=0;
  39.     for(auto edge : edges){
  40.         if(find(edge.u)==find(edge.v))
  41.             continue;
  42.         sum+=edge.w;
  43.         merge(edge.u,edge.v);
  44.     }
  45.     printf("%d",sum);
  46.     return 0;
  47. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top