POJ 1789 Truck History：最小生成樹經典應用

問題描述

給定 N (≤2000) 個卡車型號（長度 7 字符串），定義兩型號間距離為對應字符不同的個數。求連接所有型號的最小生成樹總權重（即最小化總差異）。

算法選擇

• 稠密圖（N≤2000，邊數 ~200 萬），Prim 算法 O(N²) 最優，無需建邊表。
• Kruskal O(E log E) 邊數過大，排序開銷高。

Prim 算法實現要點

距離計算

int dist(int i, int j) {
    int d = 0;
    for (int k = 0; k < 7; ++k) if (a[i][k] != a[j][k]) ++d;
    return d;
}

Prim 核心流程

int prim() {
    vector minDist(n, INF);
    vector vis(n, false);
    minDist[0] = 0;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int u = -1;
        for (int j = 0; j < n; ++j)
            if (!vis[j] && (u == -1 || minDist[j] < minDist[u])) u = j;
        vis[u] = true;
        ans += minDist[u];
        for (int v = 0; v < n; ++v)
            if (!vis[v]) minDist[v] = min(minDist[v], dist(u, v));
    }
    return ans;
}

優化技巧

• 距離矩陣預計算 mapp[i][j]，避免重複計算字符差異。
• 使用 vector 替代靜態數組，自動管理內存。
• 輸入用 cin 關閉同步或 scanf 加速。

常見坑點

• 輸入結束條件：N=0 時終止，不處理該用例。
• 輸出格式：The highest possible quality is 1/<ans>（注意題目原文輸出要求）。
• 字符串可能包含非字母字符，按 ASCII 直接比較。

複雜度分析

• 預計算距離：O(N² · 7) ≈ 2.8×10⁷ 操作，極快。
• Prim 主循環：O(N²) = 4×10⁶，總時間遠小於 1s。
• 空間：距離矩陣 2000×2000 × 2B ≈ 8 MB，安全。

總結

POJ 1789 是稠密圖 Prim 算法的教科書級例題。關鍵在於識別「完全圖 + 權重為字符差異」特徵，果斷選用 O(N²) Prim 而非 Kruskal。預計算距離矩陣、簡潔的 Prim 實現、正確的輸出格式是 AC 關鍵。