內容
有 $n$ 個物品，編號為 $1$ 到 $n$。每對物品 $(i, j)$ 之間有一個正整數距離 $D[i][j]$，其中 $D[i][i] = 0$，且 $D[i][j] = D[j][i] > 0$。
你需要將這些物品分成恰好 $k$ 組，每組至少包含一個物品，且每個物品只能分在其中一組。
分組後，對於所有 $1 \le i < j \le 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$
輸入說明
第一行包含兩個整數 $n$ 和 $k$（$2 \le k \le n \le 500$）。
接下來 $n$ 行，每行 $n$ 個整數，第 $i$ 行第 $j$ 個整數表示 $D[i][j] (0 \le D[i][j] \le 10^8)$。
子題
20%: k=2, 2 <= n <= 10
80%: 無額外限制
輸出說明
輸出一個整數，表示最大化後的最小組間距離。
範例輸入
#1
3 2 0 2 1 2 0 3 1 3 0
範例輸出
#1
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
測資資訊：
記憶體限制：
256
MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <10M
公開 測資點#7 (5%): 1.0s , <10M
公開 測資點#8 (5%): 1.0s , <10M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <10M
公開 測資點#11 (5%): 1.0s , <10M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <10M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <10M
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <10M
公開 測資點#7 (5%): 1.0s , <10M
公開 測資點#8 (5%): 1.0s , <10M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <10M
公開 測資點#11 (5%): 1.0s , <10M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <10M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <10M
提示 ：
感謝匿名網友、ysh、whale_island 提供題目敘述與範例測資
標籤:
出處:
2025年6月
APCS
[管理者：
algo.seacow@
...
(演算法海牛)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 46326 |
|
q839 | 590 | 2025-06-15 21:43 | |
| 46412 |
|
q839 | 795 | 2025-06-20 11:16 | |
| 46332 |
|
q839 | 659 | 2025-06-16 00:11 | |
| 51616 |
|
q839 | 104 | 2025-08-21 15:16 | |
| 51501 |
|
q839 | 122 | 2025-08-18 22:19 |