POJ 2075 Tangled in Cables：MST 最小生成樹求纜線長度

問題描述

給定房屋名稱及之間可鋪設纜線的路徑長度，求連接所有房屋所需的最短纜線總長。若現有纜線不足輸出 "Not enough cable"，否則輸出 "Need X miles of cable"（保留一位小數）。

解法：Prim 算法

• 用 map 將房屋名映射為 0~n-1。
• 鄰接矩陣存圖，無邊處設 INF。
• Prim 算法：lowcost[i] 表示非樹頂點 i 到樹的最小邊權。每次選最小 lowcost 入樹，更新鄰居。
• 累加 MST 總權 sum，比較給定纜線長度。

關鍵代碼片段

map mp;
double adj[200][200], lowcost[200];
bool vis[200];

void prim(int n) {
    fill(lowcost, lowcost+n, INF);
    fill(vis, vis+n, false);
    lowcost[0] = 0;
    double sum = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++)
            if (!vis[j] && (u==-1 || lowcost[j] < lowcost[u])) u = j;
        vis[u] = true;
        sum += lowcost[u];
        for (int v = 0; v < n; v++)
            if (!vis[v] && adj[u][v] < lowcost[v])
                lowcost[v] = adj[u][v];
    }
    if (sum > cableLen) puts("Not enough cable");
    else printf("Need %.1f miles of cable\n", sum);
}

輸入處理注意

輸入以字符串名稱給點，邊列表給長度。用 map 映射名稱到索引，構建鄰接矩陣。注意題目保證連通。

總結

標準 MST 應用題。Prim 算法配合字符串映射，解決「名稱索引化」與「最小連通代價」兩個子問題。輸出格式嚴格保留一位小數。