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.2cto.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