Editorial for Power Grid

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Model the problem as an MST with a virtual node.

Introduce a super-source $0$ ~0~ representing the power network. Then:

an edge from $0$ ~0~ to city $i$ ~i~ with weight $c_i$ ~c_i~ means "build a station in city $i$ ~i~";
an edge between cities $i$ ~i~ and $j$ ~j~ with weight $(k_i + k_j)\cdot(|x_i-x_j|+|y_i-y_j|)$ ~(k_i + k_j)\cdot(|x_i-x_j|+|y_i-y_j|)~ means "lay that wire".

Every city must end up connected to $0$ ~0~. The minimum cost is exactly the MST weight of this complete-ish graph on $n + 1$ ~n + 1~ nodes.

Build all $O(n^2)$ ~O(n^2)~ edges and run Kruskal. With $n \le 2000$ ~n \le 2000~ this is fine.

Solution (C++)

#include <bits/stdc++.h>
using namespace std;

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

struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[a] > sz[b]) swap(a, b);
        p[a] = b;
        sz[b] += sz[a];
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> x(n), y(n), c(n), k(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    for (int i = 0; i < n; i++) cin >> c[i];
    for (int i = 0; i < n; i++) cin >> k[i];

    vector<Edge> edges;
    edges.reserve(n * 1LL * (n - 1) / 2 + n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            long long dist = llabs(x[i] - x[j]) + llabs(y[i] - y[j]);
            edges.push_back({i, j, (k[i] + k[j]) * dist});
        }
        edges.push_back({i, n, c[i]});
    }

    sort(edges.begin(), edges.end());
    DSU dsu(n + 1);
    long long ans = 0;
    for (auto [u, v, w] : edges) {
        if (dsu.unite(u, v)) ans += w;
    }
    cout << ans << "\n";
    return 0;
}

Comments

There are no comments at the moment.