分組遊戲 (APCS 2025-06 高級)

有 \(n\) 個物品，編號 \(1\) 到 \(n\)。任兩個物品 \(i\) 與 \(j\) 之間有一個距離 \(D[i][j]\)：物品到自己的距離是 \(0\)，不同物品之間的距離是正整數，而且來回一樣遠，也就是 \(D[i][j]=D[j][i]\)。

請把這 \(n\) 個物品分成恰好 \(k\) 組，規則如下：

• 每個物品都要分進其中一組，而且只能屬於一組。
• 每一組至少要有一個物品。
• 組與組之間沒有順序之分，只看哪些物品被分在一起。

分好之後，只看分在不同組的那些物品對（同一組的兩個物品不算），它們之間距離的最小值就是這次分組的分數。請算出在所有分法中，這個分數最大能是多少。

換個說法也一樣：把同一組的 \(D[i][j]\) 全部改成無限大，再取整個距離矩陣裡剩下的最小值，並讓這個最小值盡可能大。

輸入格式

第一行有兩個整數 \(n\) 和 \(k\)，分別代表物品數與要分成的組數。

接下來有 \(n\) 行，每行 \(n\) 個整數；第 \(i\) 行的第 \(j\) 個整數就是 \(D[i][j]\)。

限制

• \(2\le k\le n\le 500\)
• \(D[i][i]=0\)；當 \(i\ne j\) 時 \(1\le D[i][j]=D[j][i]\le 10^8\)
• 因為 \(k\le n\)，一定分得出 \(k\) 組；又因為 \(k\ge 2\)，一定存在分屬不同組的物品對，所以分數一定存在

輸出格式

輸出一個整數，代表分數的最大值。

評分說明

每筆計分測資各為 5 分，範例不計分。

範例輸入 1

3 2
0 2 1
2 0 3
1 3 0

範例輸出 1

2

範例解釋 1

三個物品要分成兩組，只有三種分法：

三種分法中分數最高的是 \(\{1,3\}\)、\(\{2\}\)，所以答案為 \(2\)。

範例輸入 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

範例輸出 2

3

範例解釋 2

把五個物品分成 \(\{1,4\}\)、\(\{2,5\}\)、\(\{3\}\) 三組。分在同一組的那幾格不列入計算，以下用 - 標示：

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

剩下的距離中最小的是 \(3\)，出現在 \(D[1][5]\) 與 \(D[2][3]\)，所以這個分法的分數是 \(3\)。沒有任何分法的分數比 \(3\) 更高，所以答案為 \(3\)。

題目來源

APCS 2025 年 6 月實作題第 4 題。

題敘參考 ZeroJudge q839「分組遊戲」 整理，細節可能與正式試題有出入。