Submission #996266

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};


void solve(long long N, long long M, vector<long long> a, vector<long long> b, vector<long long> c, long long Q, vector<long long> S, vector<long long> T){
	vector< array<int,3> > es;
	for(int i = 0 ; i < M ; i++)
		es.push_back({c[i],a[i]-1,b[i]-1});
	sort(es.begin(),es.end());
	for(int i = 0 ; i < Q ; i++){
		UnionFind uf(N);
		S[i]--,T[i]--;
		uf.unionSet(S[i],T[i]);
		int ans = 0;
		for(auto e : es)
			if( uf.unionSet(e[1],e[2]) ){
				ans += e[0];
			}
		cout << ans << endl;
	}		
}



signed main(){	
	ios::sync_with_stdio(false);
	long long Q;
	long long N;
	long long M;
	cin >> N;
	cin >> M;
	vector<long long> c(M-1+1);
	vector<long long> b(M-1+1);
	vector<long long> a(M-1+1);
	for(int i = 0 ; i <= M-1 ; i++){
		cin >> a[i];
		cin >> b[i];
		cin >> c[i];
	}
	cin >> Q;
	vector<long long> T(Q-1+1);
	vector<long long> S(Q-1+1);
	for(int i = 0 ; i <= Q-1 ; i++){
		cin >> S[i];
		cin >> T[i];
	}
	solve(N, M, a, b, c, Q, S, T);
	return 0;
}

Submission Info

Judge Result