【PTA-天梯賽訓練】暢通工程之局部最小花費問題

某地區經過對城鎮交通狀況的調查，得到現有城鎮間快速道路的統計數據，並提出“暢通工程”的目標：使整個地區任何兩個城鎮間都可以實現快速交通（但不一定有直接的快速道路相連，只要互相間接通過快速路可達即可）。現得到城鎮道路統計表，表中列出了任意兩城鎮間修建快速路的費用，以及該道路是否已經修通的狀態。現請你編寫程式，計算出全地區暢通需要的最低成本。

輸入格式:

輸入的第一行給出村莊數目N (1≤N≤100)；隨後的N(N−1)/2行對應村莊間道路的成本及修建狀態：每行給出4個正整數，分別是兩個村莊的編號（從1編號到N），此兩村莊間道路的成本，以及修建狀態 — 1表示已建，0表示未建。

輸出格式:

輸出全省暢通需要的最低成本。

輸入樣例:

4
1 2 1 1
1 3 4 0
1 4 1 1
2 3 3 0
2 4 2 1
3 4 5 0

輸出樣例:

3

#include<bits/stdc++.h>
using namespace std;
int top[105];
int n,tot=0;         //連通分量初始為0 
struct edge            //邊 
{
    int x,y,w;         //x、y是邊的兩個頂點，w是邊的權值 
}a[10005];
int find(int r)
{
    if(top[r]!=r)
    top[r]=find(top[r]);
    return top[r];
}
void init(int n)
{
    for(int i=1;i<=n;i++)
        top[i]=i;
}
bool cmp(edge a,edge b) //邊從小到大排列 
{
    return a.w<b.w;
}
int join(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx!=fy)
    top[fx]=fy;
} 
int kruskal()
{
    sort(a,a+tot,cmp);
    int cnt=0,ans=0,i;
    for(i=0;i<tot;i++)
    {
        int fx=find(a[i].x),fy=find(a[i].y);
        if(fx!=fy)                              //如果路沒造 
        {
               top[fx]=fy;                         //造路 
               ans=ans+a[i].w;                     //總值增加 
               cnt++;
        } 
        if(cnt==tot-1)break;
    }
    return ans;
}
int main()
{
    int x,y,w,d,i;
    cin>>n;
    init(n);
    for(i=0;i<n*(n-1)/2;i++)
    {
        cin>>x>>y>>w>>d;
        a[tot].x=x;
        a[tot].y=y;
        a[tot++].w=w;
        if(d==1)                               //本來就連在一起的路連起來 
        join(x,y);
    }
    printf("%d\n",kruskal());
    return 0;
}