課程設計 問題 R: 自來水管道

題目描述

你領到了一個鋪設校園內自來水管道的任務。校園內有若幹需要供水的點，每兩個供水點可能存在多種鋪設路徑。對於每一種鋪設路徑，其成本是預知的。

    任務要求最終鋪設的管道保證任意兩點可以直接或間接的聯通，同時總成本最低。

輸入

每個測試用例由多行組成，第一行是兩個整數P和R，P代表供水點數（1<=P<=50），每個點都對應1到P中的一個唯一編號。R代表可能的鋪設路徑數，路徑數可能有非常多。接下有R行，每行格式如下：

節點A編號 節點B編號 路徑成本

路徑成本不超過100。

測試用例之間有一空行分開。輸入結束用P=0表示，註意沒有R值。

輸出

    每個測試用例占用一行輸出最低總成本。

樣例輸入

1 0

2 3
1 2 37
2 1 17
1 2 68

3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3 89
3 1 91
1 2 32

5 7
1 2 5
2 3 7
2 4 8
4 5 11
3 5 10
1 5 6
4 2 12

0

樣例輸出

0
17
16
26

題意：P個點，給出兩個點間的間的距離，求最小生成樹所需的成本。
思路：克魯斯卡爾演算法。將給出的邊按權值進行排序，遍歷所有的邊，如果該邊的兩個頂點不連通，則加入到生成樹中。
用sort函數排序權值。關鍵在於判斷該兩點是否連通。我用了並查集的思想。若兩點聯通則將一點的終節點指向另一點的終節點（用了數組b來存，b[i]就表示節點i指向的下一個節點）。
先初始化，讓b[i]=i。用自定義函數f(i)求i節點的終節點。如果兩節點a,b的f(a)和f(b)不想等。說明a,b,兩節點不連通。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef struct
{
    int v[3];
} p;                   //用來存兩個供水點和之間的距離
bool comp(p a, p b)    //按v[2]中的元素進行比較
{
    return a.v[2] < b.v[2];
}
p a[10000005];
int b[105];
int f(int i)          //尋找終節點
{
    if(b[i]==i) return i;
    else return f(b[i]);    //應該可以優化成 return  b[i]=f(b[i]);
}
int main()
{
    int i,t,n,s,j;
    while(scanf("%d",&n)==1&&n)
    {
        s=0;
        scanf("%d",&t);
        for(i=1; i<=t; i++)
            scanf("%d%d%d",&a[i].v[0],&a[i].v[1],&a[i].v[2]);
        sort(a,a+t,comp);
        for(i=1; i<=n; i++)
            b[i]=i;
        for(i=1; i<=t; i++)
        {
            if(f(a[i].v[0])!=f(a[i].v[1]))   //如果不連通就加入生成樹中並累加路徑
            {

                s+=a[i].v[2];
                b[f(a[i].v[0])]=f(a[i].v[1]);   //將一點的終節點指向另一點的終節點
            }
        }
        printf("%d\n",s);
    }
    return 0;
}