C++ 代码

#include <bits/stdc++.h>

using namespace std;

struct Edge {
    int u, v;
    double weight;
};

double calculateDistance(int x1, int y1, int x2, int y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int findParent(int node, vector<int>& parent) {
    if (parent[node] != node) {
        parent[node] = findParent(parent[node], parent);
    }
    return parent[node];
}

void unionSets(int u, int v, vector<int>& parent, vector<int>& rank) {
    int rootU = findParent(u, parent);
    int rootV = findParent(v, parent);
    if (rootU != rootV) {
        if (rank[rootU] < rank[rootV]) {
            parent[rootU] = rootV;
        } else if (rank[rootU] > rank[rootV]) {
            parent[rootV] = rootU;
        } else {
            parent[rootV] = rootU;
            rank[rootU]++;
        }
    }
}

double minimumAdditionalCableLength(int N, vector<pair<int, int>>& coordinates, int M, vector<pair<int, int>>& connections) {
    vector<Edge> edges;
    vector<int> parent(N), rank(N, 0);

    // Initialize union-find structure
    for (int i = 0; i < N; i++) {
        parent[i] = i;
    }

    // Union existing connections
    for (const auto& conn : connections) {
        unionSets(conn.first - 1, conn.second - 1, parent, rank);
    }

    // Generate all possible edges along with their weights
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            double distance = calculateDistance(coordinates[i].first, coordinates[i].second, 
                                                coordinates[j].first, coordinates[j].second);
            edges.push_back({i, j, distance});
        }
    }

    // Sort edges by weight
    sort(edges.begin(), edges.end(), [](Edge& a, Edge& b) {
        return a.weight < b.weight;
    });

    double totalCost = 0.0;

    // Kruskal's algorithm to find the minimum spanning tree
    for (const auto& edge : edges) {
        if (findParent(edge.u, parent) != findParent(edge.v, parent)) {
            totalCost += edge.weight;
            unionSets(edge.u, edge.v, parent, rank);
        }
    }

    return totalCost;
}

int main() {
    int N;
    cin >> N;
    vector<pair<int, int>> coordinates(N);
    for (int i = 0; i < N; i++) {
        cin >> coordinates[i].first >> coordinates[i].second;
    }

    int M;
    cin >> M;
    vector<pair<int, int>> connections(M);
    for (int i = 0; i < M; i++) {
        cin >> connections[i].first >> connections[i].second;
    }

    double result = minimumAdditionalCableLength(N, coordinates, M, connections);
    cout << fixed << setprecision(2) << result << endl;

    return 0;
}