Advertisement
Guest User

Untitled

a guest
Feb 14th, 2020
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.99 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement