poj-1287 不是题目水，而是数据弱

这个题目很简单，就是最简单的最小生成树，并且用克鲁斯卡尔算法很容易。
但是，题目中说的边可能是无限的（The number of possible routes is unlimited），如果边有很多，该如何办呢？
 
当然，这里直接开10000条以上就行了，因为测试用例有限，加入10^10条呢？
这里说了最多50个点，那么最多也就1225条边，再多就是重复的，实际上我们只需要开这么大的空间就行，然后读入所有的边，将重复的保存最小值就可以了。
不过这里没必要，因为，边数比较少。。。。
 
直接代码，要想懂得此题目，首先要看看数据结构-并查集，不过本题目用普利姆算法可能更快点，因为点少，o（n^2）.
 
[cpp] 
#include <cstdio> 
#include <iostream> 
#include <algorithm> 
using namespace std; 
 
#define nMaxEdgeNum 15000   //最大边数 
#define nMaxPointNum 100    //最多点数 
 
int father[nMaxPointNum];   //并查集模拟树的数组 
int rank[nMaxPointNum];     // 
 
typedef struct EDGE 
{ 
    int u, v, w; 
}Edge; 
Edge edge[nMaxEdgeNum]; 
 
int p, r, sum; 
 
//比较函数 
bool cmp(Edge a, Edge b) 
{ 
    return a.w < b.w; 
} 
 
//下面依次是并查集的三个函数 
//初始化 
void Init(int n) 
{ 
    for (int i = 1; i <= n; ++ i) 
    { 
        father[i] = i; 
        rank[i] = 0; 
    } 
} 
 
//查找 
int Find(int x) 
{ 
    if (x != father[x]) 
    { 
        father[x] = Find(father[x]); 
    } 
    return father[x]; 
} 
 
//合并 
void Union(int x, int y) 
{ 
    int xx = Find(x); 
    int yy = Find(y); 
    if (rank[xx] > rank[yy]) 
    { 
        father[yy] = xx; 
    } 
    else   www.zzzyk.com
    { 
        father[xx] = yy; 
        if (rank[xx] == rank[yy]) 
        { 
            rank[yy] ++; 
        } 
    } 
} 
 
//克鲁斯卡尔算法实现 
void Kruskal() 
{ 
    sum = 0; 
    Init(p); 
    sort(edge + 1, edge + r + 1, cmp); 
    for (int i = 1; i <= r; ++ i) 
    { 
        if (Find(edge[i].u) != Find(edge[i].v)) 
        { 
            sum += edge[i].w; 
            Union(edge[i].u, edge[i].v); 
        } 
    } 
    printf("%d\n",sum); 
} 
 
int main() 
{ 
    while (scanf("%d", &p) && p) 
    { 
        scanf("%d", &r); 
        for (int i = 1; i <= r; ++ i) 
        { 
            scanf("%d %d %d",&edge[i].u, &edge[i].v, &edge[i].w); 
        } 
        Kruskal(); 
    } 
 
    return 0; 
} 
作者：zhang20072844

补充：软件开发 , C++ ,