# APCS實作題2025年6月第4題：分組遊戲

> 日期：2025年6月27日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=q839)

<br />

## 題目

### 問題描述

有 $n$ 個物品，編號為 $1$ 到 $n$。每對物品 $(i, j)$ 之間有一個正整數距離 $D[i][j]$，其中 $D[i][i] = 0$，且 $D[i][j] = D[j][i] > 0$。

你需要將這些物品分成恰好 $k$ 組，每組至少包含一個物品，且每個物品只能分在其中一組。

分組後，對於所有 $1 \leq i < j \leq n$，如果物品 $i$ 和 $j$ 分在同一組，則將 $D[i][j]$ 設為 $\infty$（無限大），否則保持原距離。

接下來，考慮整個距離矩陣中剩下的 $D[i][j]$ 值（即不同組的物品之間的距離），你要最大化其中的最小值。

以範例 $2$ 為例，分成 $\{1, 4\}, \{2, 5\}, 3$，會使得距離矩陣變為（以 $-$ 標記為 $\infty$）

0 5 6 - 3
5 0 3 4 -
6 3 0 4 7
- 4 4 0 5
3 - 7 5 0

最小值為 3

<br />

### 輸入格式

第一行包含兩個整數 $n$ 和 $k$ ($2 \leq k \leq n \leq 500$)。

接下來 $n$ 行，每行 $n$ 個整數，第 $i$ 行第 $j$ 個整數表示 $D[i][j] ~(1 \leq D[i][j] \leq 10^8)$。

子題配分
- 20%：$k = 2, 2 \leq n \leq 10$
- 80%：無額外限制
<br />

### 輸出格式

輸出一個整數，表示最大化後的最小組間距離。
<br />

### 範例一：輸入

3 2
0 2 1
2 0 3
1 3 0

### 範例一：正確輸出

2

### 範例二：輸入

5 3
0 5 6 1 3
5 0 3 4 2
6 3 0 4 7
1 4 4 0 5
3 2 7 5 0

### 範例二：正確輸出

3

<br /><br />

## Python 程式碼

使用時間約為 1 s，記憶體約為 22 MB，通過測試。

from collections import deque

def check(n, k, D, x):
    """
    輸入參數：物品數量 n，分組數 k，距離 D，同組之間的最大距離 x
    運作原則：小於 x 的資料放在同一組，分組後各組之間的距離至少為 x。
    計算分組數量 cnt，如果 cnt 大於等於題目要求的分組數 k，
    可以將小組合併，符合題目的要求。
    回傳值：cnt >= k 回傳 True；反之回傳 False。
    """
    visited = [False]*n  # 走訪狀態
    cnt = 0  # 分組數
    for i in range(n):  # 掃過物品 0 ~ n-1
        if not visited[i]:  # 還沒有走訪 i
            visited[i] = True  # 已走訪 i
            cnt += 1  # 分組數加 1
            ### 用 BFS 找這個小組的成員 ###
            que = deque([i])  # 待走訪佇列，先放入 i
            while que:  # 如果 que 還有資料繼續執行
                u = que.popleft()  # 取出 que 最前面的資料
                for v in range(n):  # 掃過物品 0 ~ n-1
                    # 如果還沒有走訪 v，而且 u, v 距離小於 x，分在同一組
                    if not visited[v] and D[u][v] < x:
                        visited[v] = True  # 已走訪 v
                        que.append(v)  # v 加到 que
            ### End of BFS ###
    return cnt >= k  # 回傳 cnt 是否大於等於 k

""" 讀取資料 """
n, k = map(int, input().split())  # 物品數量 n，分組數 k
D = [list(map(int, input().split())) for _ in range(n)]  # 讀取物品之間的距離
dis_set = set()  # 所有的距離集合
for i in range(n):
    for j in range(i+1, n):
        dis_set.add(D[i][j])
dis_list = sorted(dis_set)  # 排序好的所有距離串列
""" 二分搜尋法找答案 """
low, high = 0, len(dis_list)-1  # 從 dis_list 找答案的索引值下限、上限
while low <= high:
    mid = low + (high - low) // 2
    if check(n, k, D, dis_list[mid]):  # 至少可以分成 k 組
        low = mid + 1  # 提升下限，試著用更大的距離分組
    else:  # 反之，降低上限，試著用更小的距離分組
        high = mid - 1
# 結束時 dis_list[low] 是無法分成 k 組的組間距離最小值
print(dis_list[low-1])  # 答案是 dis_list[low-1]

<br /><br />

## C++ 程式碼

使用時間約為 0.1 s，記憶體約為 7.4 MB，通過測試。

#include <cstdio>
#include <queue>
#include <vector>
#include <set>
using namespace std;

bool check(int, int, vector<vector<int>>&, int); 

int main() {
    /* 讀取資料 */
    int n, k; scanf("%d %d", &n, &k);  // 物品數量 n，分組數 k
    vector<vector<int>> D (n, vector<int> (n, 0));  // 物品之間的距離
    set<int> dis_set;  // 所有的距離集合
    for(int i=0; i<n; i++) {  // 讀取距離
        for(int j=0; j<n; j++) {
            int d; scanf("%d", &d);
            D[i][j] = d;
            D[j][i] = d;
            dis_set.insert(d);
        }
    }
    vector<int> dis_vec (dis_set.begin(), dis_set.end());  // 排序好的所有距離陣列
    /* 二分搜尋法找答案 */
    int low = 0, high = (int)dis_vec.size()-1;  // 從 dis_vec 找答案的索引值下限、上限
    while(low <= high) {
        int mid = low + (high - low) / 2;
        if (check(n, k, D, dis_vec[mid])) {  // 至少可以分成 k 組
            low = mid + 1;  // 提升下限，試著用更大的距離分組
        } else {  // 反之，降低上限，試著用更小的距離分組
            high = mid - 1;
        }
    }  // 結束時 dis_vec[low] 是無法分成 k 組的組間距離最小值
    printf("%d\n", dis_vec[low-1]);  // 答案是 dis_vec[low-1]
    return 0;
}

bool check(int n, int k, vector<vector<int>>& D, int x) {
    /* 輸入參數：物品數量 n，分組數 k，距離 D，同組之間的最大距離 x
       運作原則：小於 x 的資料放在同一組，分組後各組之間的距離至少為 x。
       計算分組數量 cnt，如果 cnt 大於等於題目要求的分組數 k，
       可以將小組合併，符合題目的要求。
       回傳值：cnt >= k 回傳 True；反之回傳 False。                        */
    vector<bool> visited (n, false);  // 走訪狀態
    int cnt = 0;  // 分組數
    for(int i=0; i<n; i++) {  // 掃過物品 0 ~ n-1
        if (!visited[i]) {  // 還沒有走訪 i
            visited[i] = false;  // 已走訪 i
            cnt++;  // 分組數加 1
            /* 用 BFS 找這個小組的成員 */
            queue<int> que;  // 待走訪佇列，先放入 i
            que.push(i);
            while(!que.empty()) {  // 如果 que 還有資料繼續執行
                int u = que.front();  // 取出 que 最前面的資料
                que.pop();
                for(int v=0; v<n; v++) {  // 掃過物品 0 ~ n-1
                    /* 如果還沒有走訪 v，而且 u, v 距離小於 x，分在同一組 */
                    if (!visited[v] && D[u][v] < x) {
                        visited[v] = true;  // 已走訪 v
                        que.push(v);  // v 加到 que
                    }
                }
            }
            /* End of BFS */
        }
    }
    return cnt >= k;
}

<br /><br />

---

###### tags:`APCS`、`C++`、`Python`