Submission #996535

---

Source Code Expand

#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <bitset>
#include <time.h>
#include <set>
#include <algorithm>
#define MAXN 4444
#define ll long long
using namespace std;

int parent[MAXN+2];
int rankk[MAXN+2];


int Find(int x) {
    if (parent[x] != x) {
        parent[x]=Find(parent[x]);
    }
    return parent[x];
}
bool Union(int x,int y) {
    int xRoot=Find(x);
    int yRoot=Find(y);
    if (xRoot==yRoot)
        return false;
    
    
    if (rankk[xRoot]<rankk[yRoot]) {
        parent[xRoot]=yRoot;
    } else if (rankk[xRoot]>rankk[yRoot]) {
        parent[yRoot]=xRoot;
    } else {
        parent[yRoot]=xRoot;
        rankk[xRoot]++;
    }
    return true;
}



int main() {
    int N,M;
    cin>>N>>M;
    vector<pair<int,pair<int,int> > > edges;
    for(int i=1;i<=M;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        edges.push_back(make_pair(w,make_pair(u,v)));
    }
    
    sort(edges.begin(),edges.end());
    
    
    
    int Q;
    cin>>Q;
    
    for(int q=1;q<=Q;q++) {
        for(int i=1;i<=N;i++) {
            parent[i]=i;
            rankk[i]=0;
        }
        int s,t;
        cin>>s>>t;
        Union(s,t);
        ll answer = 0;
        
        for(int i=0;i<edges.size();i++) {
            int u=edges[i].second.first;
            int v=edges[i].second.second;
            
            if (Union(u,v)) {
                answer+=edges[i].first;
            }
        }
        cout << answer << endl;
    }
    
    
    
    
}

Submission Info

Judge Result