HDU 1233：還是暢通工程（最小生成樹 Prim & Kruskal 雙解）

問題：N 個村莊，給出所有兩兩距離。求連通所有村莊的最小公路總長度（MST）。

Prim 算法 (鄰接矩陣 O(N²))

int Prim(int start) {
    low[start] = 0; vis[start] = 1;
    for (i=1..N) low[i] = map[start][i];
    for (j=1; j
Kruskal 算法 (邊排序 + 並查集 O(E log E))
struct Edge { int u, v, w; };
sort(edges, edges+M, [](Edge a, Edge b){ return a.w < b.w; });
for (e : edges)
    if (union(e.u, e.v)) ans += e.w;
代碼對比

Prim 矩陣版 134ms，適合稠密圖 (本題給全距離矩陣)。
Prim 鏈表版 250ms。
Kruskal 296ms，適合稀疏圖。

本題 N<100，邊數 N(N-1)/2 ≈ 5000，Prim 矩陣最快。注意輸入用 scanf 加速。