Wires

Solution Approach

Minimum Spanning Tree

Since we need to connect all points with minimum total wire length and any two points can be directly connected, this is a standard MST problem.

1. Compute all $\binom{n}{2}$ pairwise Euclidean distances.

2. Apply Kruskal's algorithm: sort edges by weight and greedily add the shortest edge that does not create a cycle, using a Union-Find data structure.

3. The MST gives the minimum total wiring length.

Why MST Is Optimal

Among all spanning trees of the complete graph, the MST minimizes the total edge weight. Since every spanning tree uses exactly $n-1$ edges and connects all nodes, the MST achieves the minimum total wire length.

Note: A Steiner tree (which may introduce additional intermediate points) could yield shorter total length, but the problem requires direct terminal-to-terminal connections.

C++ Solution

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

struct Edge {
    double w;
    int u, v;
    bool operator<(const Edge& o) const { return w < o.w; }
};

int par[55], rnk[55];

int find(int x) {
    while (par[x] != x) x = par[x] = par[par[x]];
    return x;
}

bool unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return false;
    if (rnk[a] < rnk[b]) swap(a, b);
    par[b] = a;
    if (rnk[a] == rnk[b]) rnk[a]++;
    return true;
}

double px[55], py[55];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%lf %lf", &px[i], &py[i]);

    // Build all edges
    vector<Edge> edges;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            double dx = px[i] - px[j], dy = py[i] - py[j];
            edges.push_back({sqrt(dx*dx + dy*dy), i, j});
        }

    sort(edges.begin(), edges.end());

    // Kruskal's MST
    for (int i = 0; i < n; i++) { par[i] = i; rnk[i] = 0; }

    double totalLen = 0;
    int edgesUsed = 0;
    vector<pair<int,int>> mstEdges;

    for (auto& e : edges) {
        if (unite(e.u, e.v)) {
            totalLen += e.w;
            mstEdges.push_back({e.u, e.v});
            if (++edgesUsed == n - 1) break;
        }
    }

    // Output MST edges and total length
    for (auto& [u, v] : mstEdges)
        printf("%d %d\n", u + 1, v + 1);
    printf("Total length: %.2f\n", totalLen);

    return 0;
}

Complexity Analysis

• Time complexity: $O(n^2 \log n)$. We generate $\binom{n}{2} = O(n^2)$ edges and sort them. Kruskal's algorithm with union-by-rank and path compression processes each edge in amortized $O(\alpha(n))$ time, where $\alpha$ is the inverse Ackermann function. The sorting step dominates.

• Space complexity: $O(n^2)$ for storing all edges.