#54933: 分組遊戲 Python 解題報告


tico519ml (tico)


首先這個會使用到Kruskal 演算法 再配合 DSU (Disjoint Set Union).

步驟如下

  1. 先根據輸入的2D matrix 的weight (i.e. 圖形結構的鄰接矩陣表示法),攤成1D後用weight 排序
    1D tuple (weight, i , j)
  2. 升冪排序後,從最小weight 開始把node 兩兩併成一組,用DSU做 (i.e. 如果find 相同,表示同一組,就換下一個weight組合)
  3. 組數由N開始,有合併成功就減1,直到等於K,再遇到第一個不同組的weight,該weight就是答案 (i.e. 不同組的最大化的最小距離)