問題鏈接：CCF201412試題。

問題描述：

  雷雷承包了很多片麥田，為了灌溉這些麥田，雷雷在第一個麥田挖了一口很深的水井，所有的麥田都從這口井來引水灌溉。

  為了灌溉，雷雷需要建立一些水渠，以連接水井和麥田，雷雷也可以利用部分麥田作為“中轉站”，利用水渠連接不同的麥田，這樣只要一片麥田能被灌溉，則與其連接的麥田也能被灌溉。

  現在雷雷知道哪些麥田之間可以建設水渠和建設每個水渠所需要的費用（注意不是所有麥田之間都可以建立水渠）。請問灌溉所有麥田最少需要多少費用來修建水渠。

問題分析：這是一個最小生成樹的為問題，解決的算法有Kruskal（克魯斯卡爾）算法和PRim（普里姆） 算法。

程序說明：本程序使用Prim算法實現，也許是算法復雜度的問題，，時間上超時了，只得了80分。希望有人能夠幫助改進一下。

有關最小生成樹的問題也許使用克魯斯卡爾算法，實現上更具有優勢，只需要對所有的邊進行排序后處理一遍即可。

參考鏈接：Prim算法的C語言程序。

提交后得80分的C++語言程序如下：

/* CCF201412-4 最優灌溉 */#include <iostream>#include <cstring>#include <climits>using namespace std;int main(){    int n, m, ans=0;    // 輸入數據    cin >> n >> m;    unsigned int visited[n+1], cost[n+1][n+1];    memset(visited, 0, sizeof(visited));    memset(cost, INT_MAX, sizeof(cost));    int src, dest;    for(int i=1; i<=m; i++) {        cin >> src >> dest;        cin >> cost[src][dest];        cost[dest][src] = cost[src][dest];    }    // Prim算法    unsigned int min;    int next = 1, u, v;    visited[1]=1;    while(next < n) {        min = INT_MAX;        for(int i=1; i<=n; i++)            if(visited[i] != 0)                for(int j=1; j<=n; j++)                    if(cost[i][j] < min) {                        min = cost[i][j];                        u = i;                        v = j;                    }        if(visited[u]==0 || visited[v]==0) {            next++;            ans += min;            visited[v] = 1;        }        cost[u][v] = cost[v][u] = INT_MAX;    }    // 輸出結果    cout << ans << endl;    return 0;}
另外一個提交后得80分的C++程序：
/* CCF201412-4 最優灌溉 */#include <iostream>#include <cstring>#include <climits>using namespace std;const int TRUE = 1;const int FALSE = 0;const int N = 1000;unsigned int cost[N+1][N+1];int s_set[N+1], s_count;int vs_set[N+1], vs_count;int n, m, ans = 0;// Prim算法void prim(int n){    int i, j, pj;    unsigned int minval;    for(; vs_count > 0;) {        minval = INT_MAX;        for(i=1; i<=n; i++) {            if(s_set[i])                for(j=1; j<=n; j++)                    if(i!=j && vs_set[j])                        if(cost[i][j] < minval) {                            minval = cost[i][j];                            pj = j;                        }        }        s_set[pj] = TRUE;        s_count++;        vs_set[pj] = FALSE;        vs_count--;        ans += minval;    }}int main(){    // 變量初始化    memset(cost, INT_MAX, sizeof(cost));    memset(s_set, FALSE, sizeof(s_set));    memset(vs_set, TRUE, sizeof(vs_set));    // 輸入數據    cin >> n >> m;    int src, dest;    for(int i=1; i<=m; i++) {        cin >> src >> dest;        cin >> cost[src][dest];        cost[dest][src] = cost[src][dest];    }    // Prim算法    s_set[1] = TRUE;    s_count = 1;    vs_set[1] = FALSE;    vs_count = n - 1;    prim(n);    // 輸出結果    cout << ans << endl;    return 0;}