今天寫最小生成樹~~
會提到的相關內容：

1. BFS
2. 堆結構
3. 並查集
4. 貪心
   直接放個例題來說明

例題&算法

1135. 最低成本联通所有城市
題目敘述：給一張圖(有權值)，權值代表連接兩點所需要的成本，返回連接所有點的最小成本，如果無法連接，則返回-1

[法一]Prim 貪心

思路：

1. 從哪開始，答案會是一樣的->隨意選一個起點
2. 用priority_queue(堆)實現貪心思想(利用pq來搜索路徑)
   ((取出pq最前面的元素，放入相鄰的節點))
   這個實現與理解上應該都很容易，問題是證明吧(?

WHY?

貪心法雖然好理解也好實作，可是證明卻沒有那麼的直觀
貪心法一直在找權值最小的邊，所以可以做這樣的假設
1.若一個權值最小的邊不在最小生成樹裡面
2.把這條邊加入那個不含權值最小的邊的最小生成樹
3.這時候會形成環
4.去除一條權值較大的邊(一定有，因為加入的邊是權值的)
5.形成更小的生成樹
以此發現，要選擇權值最小的邊
最後是程式碼實現~~

#define vt vector
#define pb push_back
#define iipair pair<int, int>
#define cipair pair<char, int>
#define icpair pair<int, char>
#define ispair pair<int, string>
#define sipair pair<string, int>
#define MOD 1e9+7
#define iMat vector<vector<int>>
#define cMat vector<vector<char>>
#define ll long long
#define mp make_pair
class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        //轉換成點->(點, 權重)
        vt<vt<iipair>> edges(n+1);
        for(auto con:connections){
            edges[con[0]].pb(mp(con[1], con[2]));
            edges[con[1]].pb(mp(con[0], con[2]));
        }
        priority_queue<iipair, vector<iipair>, greater<iipair> > pq;
        pq.push(mp(0, 1)); //greater<iipair>會比較pair.first
        //(cost, i)
        vt<int> vis(n+1, 0);
        int res = 0;
        int cnt = 0;
        while(!pq.empty()){
            auto top = pq.top();
            pq.pop();
            int i = top.second;
            int cost = top.first;
            if(vis[i]){
                continue;
            }
            vis[i] = 1;
            res+=cost;
            cnt++;
            for(auto edge:edges[i]){
                int next_i = edge.first;
                int next_cost = edge.second;
                if(!vis[next_i]){
                    pq.push(mp(next_cost, next_i));
                }
            }
        }
        if(cnt==n){
            return res;
        }
        return -1;
    }
};

[法二]Kruskal 並查集+貪心

思路：
1.對邊依權值排序
2.從權值小的邊開始連接
3.如果兩點未被連接過，就計算權重
4.利用並查集將連接的點並起來~~
直接放程式碼~~

class dsu{
public:
    int arr[10005];
    dsu(){
        for(int i = 0; i<10005; ++i){
            arr[i] = i;
        }
    }
    int find(int i){
        if(arr[i]==i){
            return i;
        }
        return arr[i] = find(arr[i]);
    }
    void merge(int a, int b,int w, int& cnt, int& res){ //把b並進a
        int a_head = find(a);
        int b_head = find(b);
        if(a_head!=b_head){
            cnt++;
            arr[b_head] = a_head;
            res+=w;
        }
    }
};
class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        /*
        Kruskal
        1. sort edges
        2. dsu merge
        */
        if(connections.size()<n-1){
            return -1;
        }
        auto cmp = [] (vector<int> a, vector<int> b){
            return b[2]>a[2];
        };
        dsu ddsu;
        sort(connections.begin(), connections.end(), cmp);
        int res = 0;
        int cnt = 0;
        for(int i = 0; i<connections.size()&&cnt<n-1; ++i){
            ddsu.merge(connections[i][0], connections[i][1], connections[i][2], cnt, res);
        }
        return res;
    }
};

Union權值優化

這個名字其實我不太確定(?
反正就是給並查集一個大小的權值，只把小的往大的並

class dsu{
private:
    vector<int> arr;
    vector<int> ssize;
public:
    dsu(int n){
        arr.resize(n+1);
        ssize.resize(n+1);
        for(int i = 1; i<n+1; ++i){
            arr[i] = i;
            ssize[i] = 1;
        }
    }
    int find(int i){
        if(arr[i]==i){
            return i;
        }
        return find(arr[i]);
    }
    void merge(int a, int b,int w, int& cnt, int& res){ //把b並進a
        int a_head = find(a);
        int b_head = find(b);
        if(a_head!=b_head){
            if(ssize[a_head]>ssize[b_head]){//a較大
                arr[b_head] = a_head; //b並進a
                ssize[a_head]+=ssize[b_head];
            }
            else{
                arr[a_head] = b_head;
                ssize[b_head]+=ssize[a_head];
            }
            //arr[b_head] = a_head;
            res+=w;
            cnt++;
        }
    }
};
class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        /*
        Kruskal
        1. sort edges
        2. dsu merge
        */
        int m = connections.size();
        if(m<n-1){
            return -1;
        }
        auto cmp = [] (vector<int>& a, vector<int>& b){
            return b[2]>a[2];
        };
        sort(connections.begin(), connections.end(), cmp);
        int res = 0;
        int cnt = 0;
        dsu ddsu(n);
        for(int i = 0; i<m&&cnt<n-1; ++i){
            ddsu.merge(connections[i][0], connections[i][1], connections[i][2], cnt, res);
        }
        return res;
    }
};