Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <set>
- #include <iomanip>
- #include <cmath>
- class DSU {
- std::vector<int> dsu;
- std::vector<int> sizes;
- public:
- DSU(int n) {
- for (int i = 0; i < n; ++i) {
- dsu.push_back(i);
- }
- sizes.resize(n, 1);
- }
- int find_root(int a) {
- if (dsu[a] == a) {
- return a;
- }
- return dsu[a] = find_root(dsu[a]);
- }
- void union_dsu(int a, int b) {
- if (sizes[b] < sizes[a]) {
- dsu[b] = a;
- sizes[a] += sizes[b];
- } else {
- dsu[a] = b;
- sizes[b] += sizes[a];
- }
- }
- };
- int main() {
- int N;
- std::cin >> N;
- int a, b;
- std::vector<std::vector<double>> matrix(N, std::vector<double>(N, 0));
- std::vector<std::pair<int, int>> points(N);
- for (int i = 0; i < N; ++i) {
- std::cin >> a >> b;
- points[i] = std::make_pair(a, b);
- }
- double s;
- for (int i = 0; i < N; ++i) {
- for (int j = i + 1; j < N; ++j) {
- s = std::pow(std::pow(points[i].first - points[j].first, 2) + std::pow(points[i].second - points[j].second, 2), 0.5);
- matrix[i][j] = s;
- }
- }
- int M;
- std::cin >> M;
- for (int i = 0; i < M; ++i) {
- std::cin >> a >> b;
- matrix[a - 1][b - 1] = 0;
- matrix[b - 1][a - 1] = 0;
- }
- std::vector<std::pair<double, std::pair<int, int>>> lines;
- for (int i = 0; i < N; ++i) {
- for (int j = i + 1; j < N; ++j) {
- lines.push_back(std::make_pair(matrix[i][j], std::make_pair(i, j)));
- }
- }
- DSU dsu(N);
- std::sort(lines.begin(), lines.end());
- double answer = 0;
- for (int i = 0; i < lines.size(); ++i) {
- double s = lines[i].first;
- int a = lines[i].second.first;
- int b = lines[i].second.second;
- int r1 = dsu.find_root(a);
- int r2 = dsu.find_root(b);
- if (r1 != r2) {
- answer += s;
- dsu.union_dsu(r1, r2);
- }
- }
- std::cout << std::setprecision(5) << answer << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement