1584. Min Cost to Connect All Points
解題說明
Min Cost to Connect All Points
題目描述：給定平面上 n 個點的座標陣列 points，其中 points[i] = [xi, yi]。連接任意兩點的代價為其曼哈頓距離 |xi - xj| + |yi - yj|。回傳連接所有點所需的最小總代價（即最小生成樹 Minimum Spanning Tree 的總權重）。
解題思路：此題直接對應圖論中的**最小生成樹（MST）*問題。所有點兩兩之間都有邊（完全圖），共有 n(n-1)/2 條邊，邊的權重為曼哈頓距離。
使用 Prim's Algorithm（普林演算法） 搭配最小堆：
- 初始化：從第 0 個點出發，將其到所有其他點的距離加入最小堆
(cost, next_node)。 - 貪心擴張：每次從堆中取出代價最小的邊，若目標節點尚未加入 MST，則將其納入 MST，累加代價，再將此節點到所有未訪問鄰居的距離推入堆。
- 終止條件：當 MST 包含 n 個節點時完成。
Prim vs Kruskal 的選擇：本題為稠密完全圖（每對點之間都有邊），Prim's 演算法的效率優於 Kruskal's。Kruskal's 需要先枚舉並排序所有 O(n²) 條邊，而 Prim's 可以動態選擇最短邊，在稠密圖上通常更快。
曼哈頓距離計算：abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])，注意使用絕對值。
C++ 解法
複雜度分析
時間複雜度：O(n² log n) — 外層迴圈最多執行 n 次（每次加入一個節點），每次加入節點後向堆推入最多 n 條邊。堆的大小最壞情況為 O(n²)，每次 push/pop 操作為 O(log n²) = O(log n)，總計 O(n² log n)。
空間複雜度：O(n²) — 最壞情況下最小堆儲存 O(n²) 個元素（所有點對的邊）。inMST 陣列需 O(n)。
虛擬碼
1. Initialize min-heap pq with (0, 0) [cost=0, start from point 0]
2. Initialize inMST[n] = {false}, totalCost = 0, nodesAdded = 0
3. While nodesAdded < n:
a. Pop (cost, u) from pq (minimum cost entry)
b. If inMST[u]: skip (continue)
c. Mark inMST[u] = true, totalCost += cost, nodesAdded++
d. For each unvisited point v:
- dist = Manhattan distance between points[u] and points[v]
- Push (dist, v) to pq
4. Return totalCost其他解法
Kruskal's Algorithm O(n² log n)：預先枚舉所有 n*(n-1)/2 條邊並按權重排序，再用 Union-Find 貪心地加入不形成環的邊，直到 n-1 條邊選完。與 Prim's 時間複雜度相同，但需要額外 O(n²) 空間儲存所有邊。對稀疏圖（邊數遠少於 n²）更有優勢，但本題為完全圖，Prim's 通常更快。
優化版 Prim's（無堆）O(n²)：對完全圖可以不使用最小堆，而是維護一個 minDist[] 陣列記錄每個未加入節點到 MST 的最短距離。每輪線性掃描找最小值（O(n)），加入後更新所有未訪問節點的距離（O(n)），共 n 輪，總計 O(n²)。此版本對本題更優，因為 n 最大為 1000，O(n²) = O(10⁶) 完全可接受。
延伸思考
- 若將曼哈頓距離改為歐氏距離（√((x1-x2)²+(y1-y2)²)），演算法邏輯是否仍然正確？計算浮點數距離時有哪些精度問題需要注意？
- 本題的「優化版 Prim's（無堆）O(n²)」在 n=1000 時比「堆版 O(n² log n)」快，但當 n 增大到什麼規模時，兩者的實際效能差異會更為明顯？
- 最小生成樹有一個重要性質：MST 上任意兩點之間的路徑，是所有連通路徑中「最大邊權重最小」的一條（Minimax Path）。如何利用已建好的 MST 來快速回答「從點 A 到點 B 的路徑上，最大曼哈頓距離是多少」這類查詢？