Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int n,m;
- int parent[100001];
- int find(int u) {
- if (parent[u] == u)
- return u;
- return parent[u] = find(parent[u]);
- }
- void merge(int u, int v) {
- u = find(u), v = find(v);
- if (u == v)
- return ;
- parent[u] = v;
- }
- struct Edge {
- int u,v,w;
- bool operator <(const Edge & rhs) const{
- return w< rhs.w;
- }
- };
- vector <Edge> edges;
- int main(){
- scanf("%d",&n);
- int weight[n+1];
- for(int i=1;i<=n;i++){
- scanf("%d ",&weight[i]);
- }
- scanf("%d",&m);
- for(int i=1;i<=m;i++){
- int u,v;
- scanf("%d %d",&u,&v);
- edges.push_back({u,v,weight[u]+weight[v]});
- parent[u]=u;
- parent[v]=v;
- }
- sort(edges.begin(),edges.end());
- int sum=0;
- for(auto edge : edges){
- if(find(edge.u)==find(edge.v))
- continue;
- sum+=edge.w;
- merge(edge.u,edge.v);
- }
- printf("%d",sum);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement