Submission #3315215

---

Source Code Expand

#include<iostream>

#include <vector>
#include <list>
#include<stack>
#include<queue>
#include<array>

#include <set>
#include<map>

#include<string>
#include<stdlib.h>

#include<algorithm>
#include <functional>
#include<math.h>

#include<fstream>
#include<iomanip>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int,int>;

#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl

constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 1000000007;// 10^9+7


//変数


class UnionFind {
public:
	vector<int>rank, parent;
	//初期化
	UnionFind(int size) {
		rank.resize(size, 0);
		parent.resize(size, 0);
		REP(i, size)parent[i] = i;
	}
	//木の根を求める
	int find(int x) {
		if (parent[x] == x)return x;
		else return parent[x] = find(parent[x]);
	}
	//xとyの属する集合を併合
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y)return;
		if (rank[x] < rank[y])
			parent[x] = y;
		else {
			parent[y] = x;
			if (rank[x] == rank[y])rank[x]++;
		}
	}
	//xとyが同じ集合に属するか否か
	bool same(int x, int y) {
		return (find(x) == find(y));
	}
};


struct Edge { ll u, v, cost; };
bool comp(const Edge& r1, const Edge& r2) {
	return r1.cost < r2.cost;
}

int N, M, Q;
vector<Edge> edges;
vector<pair<ll, ll>> st;

//サブ関数
//入力
void input()
{
	cin >> N >> M;

	int a, b, c;
	REP(i, M) {
		cin >> a >> b >> c;
		a--; b--;
		edges.push_back({ a,b,c });
	}
	cin >> Q;
	REP(i, Q) {
		cin >> a >> b;
		a--; b--;
		st.push_back({ a,b });
	}
}

vector<Edge> kruskal() {
	UnionFind uf(N);
	vector<Edge> res;

	sort(edges.begin(), edges.end(), comp);
	for (auto e : edges) {
		if (!uf.same(e.u, e.v)) {
			uf.unite(e.u, e.v);
			res.push_back(e);
		}
	}
	return res;
}

ll kruskal(vector<Edge> edges) {
	UnionFind uf(N);
	ll res = 0;

	sort(edges.begin(), edges.end(), comp);
	for (auto e : edges) {
		if (!uf.same(e.u, e.v)) {
			uf.unite(e.u, e.v);
			res += e.cost;
		}
	}
	return res;
}


//計算
void calc()
{
	auto minimalTree = kruskal();
	for (const auto& p : st) {
		auto graph = minimalTree;
		graph.push_back({ p.first,p.second,0 });
		cout << kruskal(graph) << endl;
	}
}


//出力
void output()
{

}


//デバッグ
void debug()
{
	int N;
	cin>>N;
}


//メイン関数
int main()
{
	input();
	calc();
	output();
	debug();
	
	return 0;
}

Submission Info

Judge Result