問(wèn)題鏈接：CCF201412試題。

問(wèn)題描述：

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

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

  現(xiàn)在雷雷知道哪些麥田之間可以建設(shè)水渠和建設(shè)每個(gè)水渠所需要的費(fèi)用（注意不是所有麥田之間都可以建立水渠）。請(qǐng)問(wèn)灌溉所有麥田最少需要多少費(fèi)用來(lái)修建水渠。

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

程序說(shuō)明：本程序使用Prim算法實(shí)現(xiàn)，也許是算法復(fù)雜度的問(wèn)題，，時(shí)間上超時(shí)了，只得了80分。希望有人能夠幫助改進(jìn)一下。

有關(guān)最小生成樹(shù)的問(wèn)題也許使用克魯斯卡爾算法，實(shí)現(xiàn)上更具有優(yōu)勢(shì)，只需要對(duì)所有的邊進(jìn)行排序后處理一遍即可。

參考鏈接：Prim算法的C語(yǔ)言程序。

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

/* CCF201412-4 最優(yōu)灌溉 */#include <iostream>#include <cstring>#include <climits>using namespace std;int main(){    int n, m, ans=0;    // 輸入數(shù)據(jù)    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;    }    // 輸出結(jié)果    cout << ans << endl;    return 0;}
另外一個(gè)提交后得80分的C++程序：
/* CCF201412-4 最優(yōu)灌溉 */#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));    // 輸入數(shù)據(jù)    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);    // 輸出結(jié)果    cout << ans << endl;    return 0;}