分組遊戲 題解｜APCS 2025 年 6 月高級 第 4 題

前置知識

這題是最小生成樹（Kruskal）換個問法，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 併查集：NTUCPC Guide〈併查集〉——「這兩個東西在同一組嗎」和「把兩組併成一組」各做到幾乎 \(O(1)\)；吳邦一《AP325》第 7 章 7.4.2 用「社團與社長」講同一套（教材 PDF 第 253～259 頁；Python 版第 7 章（III））。
• 最小生成樹與 Kruskal 演算法：NTUCPC Guide〈最小生成樹〉——邊由小到大看，兩端還沒連通就選進來；《AP325》7.4.3 的 P-7-12 就是它的裸題（教材 PDF 第 260～266 頁，站上題目 ap325p712）。本題要帶走的是「依距離由小到大合併」這個動作，連生成樹本身都不用建出來。
• 用整數的位元枚舉子集（子題組 1 用）：NTUCPC Guide〈枚舉〉的「集合」一節——\(n\) 個物品的每一種「選或不選」對應 \(0\) 到 \(2^n - 1\) 的一個整數。

簡潔題意

\(n\) 個物品，任兩個之間有距離 \(D[i][j] = D[j][i]\)。把它們分成恰好 \(k\) 組（每組至少一個），分組的分數＝所有「分在不同組」的物品對之中距離最小的那個。求分數最大能是多少（\(2 \le k \le n \le 500\)，\(1 \le D[i][j] \le 10^8\)）。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(20\) 分）：\(n \le 10\) 且 \(k = 2\)。
• 子題組 2（\(80\) 分）：無額外限制。

先拿下 20 分：枚舉第一組是誰

\(k = 2\) 時只要決定「哪些物品在第一組」，剩下的就是第二組。\(n \le 10\)，用一個整數 mask 的第 \(i\) 個位元代表物品 \(i\) 在不在第一組，\(2^{10} = 1024\) 種全部試一遍，每種掃全部物品對算分數：

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

int main() {
    int n, k;
    cin >> n >> k;                                   // 子題組 1 保證 k = 2
    vector<vector<int>> d(n, vector<int>(n));
    for (auto &row : d)
        for (int &v : row) cin >> v;

    int best = 0;
    for (int mask = 1; mask < (1 << n) - 1; mask++) {   // 第 i 個 bit 是 1：物品 i 在第一組；全 0、全 1 會有一組空的，跳過
        int score = INT_MAX;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if ((mask >> i & 1) == 1 && (mask >> j & 1) == 0)   // i 在第一組、j 在第二組
                    score = min(score, d[i][j]);
        best = max(best, score);
    }
    cout << best << '\n';
    return 0;
}

\(1024 \times 100\) 次，子題組 1 的 \(20\) 分穩穩到手。\(n = 500\) 時 1 << n 連整數都裝不下，更別說 \(2^{500}\) 種分法。

從 20 分到 100 分：距離太短的兩個物品一定要同組

反過來問：分數有沒有辦法至少是 \(D\)？ 分數是「跨組距離的最小值」，要讓它 \(\ge D\)，所有距離小於 \(D\) 的物品對都不能跨組——必須同組。而且同組會傳染：\(1\) 和 \(2\) 必須同組、\(2\) 和 \(3\) 必須同組，那 \(1\) 和 \(3\) 也被綁在一起了。把「距離 \(< D\)」的物品對都當成一條邊，被邊連在一起的物品就是一塊，一塊只能整塊放進同一組。

• 塊數 \(\ge k\)：做得到。每塊當一組，多出來的塊隨便併進別組——併組只會讓更多的物品對「不算分」，跨組的距離仍然全部 \(\ge D\)。
• 塊數 \(< k\)：做不到。組數不夠分，一定有某一塊被拆開，拆開的那一刀就切到一條 \(< D\) 的邊。

所以答案＝最大的 \(D\)，使得「距離 \(< D\) 的邊」連出來的塊數 \(\ge k\)。\(D\) 不用一個一個試：把全部 \(\frac{n(n-1)}{2}\) 條邊依距離由小到大排好，從每個物品自成一組開始，一條一條看——兩端已經同組就跳過，不同組就併起來（塊數減 \(1\)）。併到剛好剩 \(k\) 塊時停下來：此時下一條「兩端不同組」的邊距離是 \(w\)，那麼 \(D = w\) 做得到（比 \(w\) 短的邊全在組內），\(D\) 再大一點就得把這條邊也併進去、塊數少於 \(k\)——答案就是 \(w\)（圖 1）。這正是 Kruskal 演算法走到一半的樣子，差別只在：我們要的不是最後併的那條邊，而是停下來之後的下一條跨組邊。

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

const int MAX_N = 505;
int parent[MAX_N];

int findRoot(int u) {                    // 併查集：找 u 這一組的代表，順便路徑壓縮
    if (parent[u] == u) return u;
    return parent[u] = findRoot(parent[u]);
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<tuple<int, int, int>> edges;  // (距離, i, j)，每對物品只收一次
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            int v;
            cin >> v;
            if (i < j) edges.push_back({v, i, j});
        }
    sort(edges.begin(), edges.end());    // 距離由小到大

    for (int i = 0; i < n; i++) parent[i] = i;   // 一開始每個物品自己一組
    int groups = n;
    for (auto [w, i, j] : edges) {
        int a = findRoot(i), b = findRoot(j);
        if (a == b) continue;            // 已經同組，這一對不會被算分
        if (groups == k) {               // 剛好 k 組了：這是最短的跨組距離，就是答案
            cout << w << '\n';
            return 0;
        }
        parent[a] = b;                   // 距離太短的兩組併成一組
        groups--;
    }
    return 0;
}

\(k = n\) 時一次都不用併，第一條邊（全場最短的距離）就是答案——程式一進迴圈 groups == k 就成立，自然印對。邊最多 \(\frac{500 \times 499}{2} = 124750\) 條，排序 \(O(n^2 \log n)\)，\(n = 500\) 本站實測不到 \(0.1\) 秒。

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

const int MAX_N = 505;
int n, k;
int d[MAX_N][MAX_N];
int parent[MAX_N];

int findRoot(int u) {
    if (parent[u] == u) return u;
    return parent[u] = findRoot(parent[u]);
}

bool canScore(int limit) {               // 分數有沒有辦法 >= limit？
    for (int i = 0; i < n; i++) parent[i] = i;
    int groups = n;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (d[i][j] < limit) {       // 距離不到 limit 的兩個物品被迫同組
                int a = findRoot(i), b = findRoot(j);
                if (a != b) {
                    parent[a] = b;
                    groups--;
                }
            }
    return groups >= k;                  // 被迫併出來的組數夠分成 k 組就行（多的組可以再合併）
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> d[i][j];

    int lo = 1, hi = 100000000;          // 答案一定在 [lo, hi]：lo 可行、hi 之外不用看
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (canScore(mid)) lo = mid;     // mid 可以，答案至少是 mid
        else hi = mid - 1;               // mid 不行，更大的也不行
    }
    cout << lo << '\n';
    return 0;
}

測過再交：範例裡沒有 \(k = n\)，也沒有「要跳過同組邊」的局面

範例 1 併一次就停、範例 2 併兩次就停，停下來的下一條邊剛好都是跨組的。沒蓋到的：\(k = n\) 一次都不併、距離全部相同、停下來之後先遇到同組的邊、值域極端。

五筆都親眼看過正確，這題就穩了。