TIOJ 1727：Spore

TIOJ 1727：Spore

題目大意：平面上有 $n$ 個點，給你 $n$ 個點的座標，這 $n$ 個點想要可以直接或間接通訊，兩個點可以直接通訊的方式有兩種，第一種是接電纜，價格為兩點距離平方，第二種是兩點都設有收發器，每一點設置收發器的價格為 $C_i$，並且你最多只能在 $k$ 個點設收發器，問你最小花費可以是多少。

解法：首先答案有兩種可能，一種是整張圖連通，不用設任何收發器，那我們可以直接求最小生成樹，第二種是要設收發器，於是我們可以考慮在最小生成樹上樹背包，令 $\text{dp}_{0, i}$ 代表目前的連通塊沒有設收發器，並且之前已經設了 $i$ 個收發器，$\text{dp}_{1, i}$ 代表目前的連通塊有設收發器，並且之前已經設了 $i$ 個收發器，然後令 $\text{val}_0, \text{val}_1$ 為子樹的 $\text{dp}$ 值，那可以列出 $\text{dp}$ 式：$\text{dp}_0 = \max (\text{dp}_0 + \text{val}_0, \text{dp}_0+\text{val}_1+w)$，$\text{dp}_1 = \max (\text{dp}_0+\text{val}_0 - c, \text{dp}_0 + \text{val}_1, \text{dp}_1 + \text{val}_0, \text{dp}_1+\text{val}_1+w)$。這個式子看起來是 $O(nk^2)$ 的，但實際上只要維護目前到達的大小，那可以證明複雜度為 $O(nk)$，最後複雜度為 $O(n^2\log(n)+nk)$ 或 $O(n^2+nk)$，看是用 $\text{Kruskal}$ 還是 $\text{Prim}$。

$\text{Code：}$

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

using ll = long long;
using DP = vector<ll>;

const ll INF = 1e18;
const int N = 2005;
const int M = N * N / 2;

int n, m, k;
ll sum, ans;
int to[N], h[N];
int x[N], y[N], a[N];
tuple<int, int, int> e[M];
vector<pair<int, int>> adj[N];

int dsu (int x) {
    return x == to[x] ? x : (to[x] = dsu (to[x]));
}

bool Merge (int a, int b) {
    a = dsu (a), b = dsu (b);
    if (a == b) return 0;
    if (h[a] < h[b]) swap (a, b);
    to[b] = a;
    h[a] += h[a] == h[b];
    return 1;
}

void Merge (DP &dp, DP a, DP b, int w, int c = -1) {
    int siz = dp.size() - 1;
    if (c >= 0) {
        a.emplace_back (0);
        for (int i = a.size() - 1; i >= 1; i--) a[i] = a[i - 1] - c;
        a[0] = -INF;
    }
    if (a.size() + b.size() - 2 > siz) {
        siz = min (k, (int) (a.size() + b.size() - 2));
        dp.resize (siz + 1, -INF);
    }
    for (int i = 0; i < a.size(); i++) for (int j = 0; j < b.size() && i + j <= siz; j++) {
        dp[i + j] = max (dp[i + j], a[i] + b[j] + w);
    }
}

pair<DP, DP> dfs (int pos, int fa) {
    DP dp0 (1, 0), dp1 (2, -INF);
    dp1[1] = -a[pos];
    for (auto [np, w] : adj[pos]) if (np != fa) {
        auto [val0, val1] = dfs (np, pos);
        DP ndp0 (1, -INF), ndp1 (1, -INF);
        Merge (ndp0, dp0, val0, 0);
        Merge (ndp0, dp0, val1, w);
        Merge (ndp1, dp0, val0, 0, a[pos]);
        Merge (ndp1, dp0, val1, 0);
        Merge (ndp1, dp1, val0, 0);
        Merge (ndp1, dp1, val1, w);
        dp0 = ndp0;
        dp1 = ndp1;
    }
    return {dp0, dp1};
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    int tt;
    cin >> tt;
    while (tt--) {
        cin >> n >> k;
        k = min (k, n);
        for (int i = 1; i <= n; i++) {
            to[i] = i;
            h[i] = 0;
            adj[i].clear();
            cin >> x[i] >> y[i] >> a[i];
        }
        m = sum = ans = 0;
        for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) e[++m] = {(x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]), i, j};
        sort (e + 1, e + m + 1);
        for (int i = 1; i <= m; i++) {
            auto [w, a, b] = e[i];
            if (Merge (a, b)) {
                sum += w;
                adj[a].emplace_back (b, w);
                adj[b].emplace_back (a, w);
            }
        }
        DP dp = dfs (1, 1).second;
        ans = sum;
        for (int i = 2; i < dp.size(); i++) ans = min (ans, sum - dp[i]);
        cout << ans << '\n';
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！