Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <queue>
- #include <tuple>
- #include <vector>
- using namespace std;
- struct point {
- int x, y;
- point(int x_, int y_) :
- x(x_), y(y_) {}
- };
- int find_root(vector<int> &reps, int vert) {
- vector<int> path;
- while (reps[vert] != vert) {
- path.push_back(vert);
- vert = reps[vert];
- }
- for (size_t i = 0; i < path.size(); ++i) {
- reps[path[i]] = vert;
- }
- return vert;
- }
- void uniot_set(vector<int> &reps, vector<int> &ranks, int first_v, int second_v) {
- int first_root = find_root(reps, first_v);
- int second_root = find_root(reps, second_v);
- if (ranks[first_root] > ranks[second_root]) {
- reps[second_root] = first_root;
- } else if (ranks[first_root] == ranks[second_root]) {
- reps[second_root] = first_root;
- ++ranks[first_root];
- } else {
- reps[first_root] = second_root;
- }
- }
- int main() {
- int N;
- cin >> N;
- vector<point> points;
- points.reserve(N);
- for (int i = 0; i < N; ++i) {
- int x, y;
- cin >> x >> y;
- points.emplace_back(x, y);
- }
- vector<int> reps;
- reps.assign(N, 0);
- for (int i = 0; i < N; ++i) {
- reps[i] = i;
- }
- vector<int> ranks;
- ranks.assign(N, 1);
- vector<pair<double, pair<int, int>>> graph;
- for (int i = 0; i < N; ++i) {
- for (int j = i + 1; j < N; ++j) {
- double weight = sqrt(pow(points[i].x - points[j].x, 2) + pow(points[i].y - points[j].y, 2));
- graph.emplace_back(weight, make_pair(i, j));
- }
- }
- sort(graph.begin(), graph.end());
- int M;
- cin >> M;
- for (int i = 0; i < M; ++i) {
- int first_v, second_v;
- cin >> first_v >> second_v;
- --first_v, --second_v;
- uniot_set(reps, ranks, first_v, second_v);
- }
- double cost = 0;
- for (size_t i = 0; i < graph.size(); ++i) {
- double weight = graph[i].first;
- int first_v = graph[i].second.first;
- int second_v = graph[i].second.second;
- if (find_root(reps, first_v) != find_root(reps, second_v)) {
- uniot_set(reps, ranks, first_v, second_v);
- cost += weight;
- }
- }
- cout << cost;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement