有 $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%: 無額外限制
輸出一個整數，表示最大化後的最小組間距離。
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
感謝匿名網友、ysh、whale_island 提供題目敘述與範例測資
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||