CCF201412-4 最优灌溉（80分）

问题链接：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;}