---
tags: 演算法
title: Kruskal 演算法
---
## Kruskal 演算法
### 解決 最小生成樹(MST) 問題
> 在 **稀疏圖** 表現較佳
> 需要用到 **並查集** 檢查連通

### 核心思想
> 將每條 **邊(edge)** 用 權重 排序
> 一條一條取 直到將整張圖的每個節點連起來為止

> 因此需要用到 並查集 來決定要不要取
> ---> 如果 這條邊上的兩個點 **沒有連通** 才取
>
> 結束條件 : 直到取了 **V - 1** 條邊 ------------------- (把 V 個點串起來最少的邊 應該很好理解)

### 實作技巧
> 定義一個 class edge 然後定義他的 operator< 用權重排序
> 會用到 **"並查集"** ---> 筆記裡面有

#### 我踩過的坑
- 如果 class 自己寫了一個建構子 請在補一個 空白的給他 不然 allocator 會出錯

### 相關題目
UVa 908:
> ~~這題目很坑~~ 看了一個小時才看懂 ~~(我就爛)~~ 總之講了一堆廢話
> 需要輸出 舊的花費 跟 新的花費
> 第一筆資料的權重加起來就是答案 第二筆+第三筆是新的邊 -> 求最小花費
> 喔對了 結束那行不用換行
> ~~哭啊~~

#include "bits/stdc++.h"
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;

class edge{
  public:
    int s,e,w;
    edge(int x,int y,int z):s(x),e(y),w(z){}
    edge(){}
};
bool operator<(edge a,edge b){
    return a.w < b.w;
}

//並查集
vector<int> f,Rank;
void UFinit(int V){
    f.resize(V+1);
    Rank.resize(V+1);
    for(int i=0;i<=V;i++)
        f[i] = i;
}
int Find(int x){
    return x == f[x] ? x : f[x] = Find(f[x]);
}
void Union(int x,int y){
    if (Rank[x] < Rank[y])
        f[x] = y;
    else{
        if (Rank[x] == Rank[y])
            Rank[x]++;
        f[y] = x;
    }
}

int main() {

    int V; 
    bool f = 1;  //處理最後不換行的問題
    while(cin>>V){
        if(!f)
            cout<<endl;
        f = false;
        vector<edge> gp;
        UFinit(V);
        
        int oldcost=0;
        for(int i=1;i<V;i++){
            int s, e, w; cin>>s>>e>>w;
            oldcost+=w;
        }
        int add; cin >> add;
        while(add--){
            int s, e, w; cin>>s>>e>>w;
            gp.push_back(edge(s,e,w));
        }
        cin >> add;
        while (add--) {
            int s, e, w; cin >> s >> e >> w;
            gp.push_back(edge(s, e, w));
        }
        
        // Kruskal Algorithm
        int cost = 0, e_count = 0;
        sort(gp.begin(),gp.end());
        for(int i=0;i<gp.size();i++){
            int a = Find(gp[i].s),b = Find(gp[i].e);
            if(a!=b){
                Union(a,b);
                cost += gp[i].w;
                e_count++;
            }
            if(e_count==V-1)
                break;
        }

        cout << oldcost << endl
             << cost << endl;
    }
    return 0;
}