Problem 10034 Freckles 雀斑

這題是標準的最小伸展樹(Minimum Spanning Tree)問題(或稱為最小生成樹)，可以使用 Prim 或 Kruskal 演算法來解決，不需要自己再發明什麼新的方法。

這裡使用 Prim 的演算法，參考蔡宗翰譯的「演算法--使用C++虛擬碼」書中(碁峯資訊，2004年)，第四章貪婪演算法的方式，很快就可以完成。
在讀取雀斑輸入值之座標點後，你必須自行製作 W 距離矩陣，W 是全域變數，提供 prim 函數使用。另一個全域變數 F ，用來存放解答中相連的點。
prim 函數如下：

void prim(int m)
{
    int i,j,k,vnear;
    int nearest[SIZE];
    float distance[SIZE], Dmin;
    for (i=1; i<m; i++)
    {
        nearest[i] = 0; /* Start from v0 */
        distance[i] = W[0][i];
    }
    for (k=1;k<m;k++)
    {
        Dmin = inf;
        for (i=1;i<m;i++)
            if (0<=distance[i] && distance[i]<Dmin)
            {
                Dmin = distance[i];
                vnear = i;
            }
        F[k][0] = vnear;
        F[k][1] = nearest[vnear];
        
        distance[vnear] = -1;
        for (i=1;i<m;i++)
            if (W[i][vnear] < distance[i])
            {
                distance[i] = W[i][vnear];
                nearest[i] = vnear;
            }
    }
}

當完成10034 Freckles，ACM 10147 Highways (高速公路)與 ACM 10397 Connect the Campus(連接校園) 這兩題就可以順便輕鬆的解題了。
p10034題目連結
回ACM題庫目錄
回首頁