# MST最小生成樹

## Prim's algorithm O(mn)

### 介紹
普林演算法的方式是，隨意選定一個節點當頂點，從頂點開始延伸選擇最小的邊連接的節點放入最小生成樹的集合中，再將形成的生成樹所連接到的節點，選擇最小的邊所連接的節點，一直反覆操作並比對是否形成迴圈，直到最小生成樹確實放入所有節點為止。

簡單說就是，隨機選點，把此點所有連線的點加入備取，備取路徑最短的點就是你要走的下一個點，同時要注意不能走過又再走一次，會形成環。以下面的圖當例子












這樣我們就簡單完成了最小生成樹的作法
##
### 實作:

#include <bits/stdc++.h>
using namespace std;

struct se{
    int bond;
    int val;
};

vector <se> tree[100005];
bool check_if [100005]={0};
int box[100005] = {0} ;
vector<int> wait_line ; 

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m, x;
    se next;
    cin >> m ;
    for(int i = 0 ; i < m ; i++){
        cin >> x >> next.bond >> next.val;
        tree[x].push_back(next);
        x ^= next.bond;
        next.bond ^=x;
        x ^= next.bond;
        tree[x].push_back(next);
    }
    
    long long int  ans = 0;
    check_if[0] = true;
    for(auto it : tree[0]) if(it.bond < n) box[it.bond] = it.val , wait_line.push_back(it.bond);
    
    while(!wait_line.empty()){
        int now = INT_MAX , now_str = 0 ;
        vector<int>::iterator now_it ;
        for(auto it = wait_line.begin() ; it !=  wait_line.end() ; it ++){
            if(box[*it] < now) now = box[*it] , now_str = *it , now_it = it;
        }
        wait_line.erase(now_it);
        check_if[now_str]=true;
        for(auto iter : tree[now_str]){
            if(check_if[iter.bond] == false) {
                if(box[iter.bond]==0) {
                    wait_line.push_back(iter.bond);
                    box[iter.bond] = iter.val;
                }else{
                    box[iter.bond] = min(box[iter.bond],iter.val);
                }
            }
        }
        ans += now;
    }

    cout << ans << '\n';
    return 0;
}

## Prim's algorithm 搭配dijkstra O(mlogm)

### 優化
在找尋最小路徑的時候，其實不用對所有的備取名單做遍歷，我們可以用一個支援插入，刪除最小值，取得最小值的資料結構來維護。這邊實作採用priority queue來維護。

### 實作

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int> 

struct se{
    int bond;
    int val;
};

priority_queue <pii,vector<pii>,greater<pii>> pq ;
int main() {
    //ios::sync_with_stdio(false), cin.tie(0);
    int n, m, x;
    se next;
    while(cin >> n){
        cin >> m ;
        vector <se> tree[100005];
        bool check_if [100005]={0};
        for(int i = 0 ; i < m ; i++){
            cin >> x >> next.bond >> next.val;
            tree[x].push_back(next);
            x ^= next.bond;
            next.bond ^=x;
            x ^= next.bond;
            tree[x].push_back(next);
        }
        long long int check = 1, ans = 0;
        check_if[0] = true;
        for(auto it : tree[0]){ 
            if(it.bond < n) {
                pq.push({it.val,it.bond});
            }
        }
        while(!pq.empty()){
            auto it = pq.top();
            bool ch = false;
            while(!pq.empty()){
                it = pq.top();
                if(check_if[it.second]==true){
                    pq.pop();
                }else{
                    ch = true;
                    break;
                };
            }
            if(!ch) break;
            pq.pop();
            check_if[it.second]=true;
            for(auto iter : tree[it.second]){
                if(iter.bond < n && check_if[iter.bond] == false) 
                    pq.push({iter.val,iter.bond});
            }
            check++;
            ans += it.first;
        }
        if(check == n) cout << ans << '\n';
        else cout << "-1" << '\n';
    }

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int n, m , x , y;
    cin >> n >> m >> x >> y;
    vector<vector<pair<int,pair<int,int>>>> G(n);
    vector<int> dis(n,1ll<<60);
    for (int i = 0 ; i < m ; i++) {
        int a, b, t, k;
        cin >> a >> b >> t >> k;
        a--, b--;
        G[a].push_back({b,{t,k}});
        G[b].push_back({a,{t,k}});
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    auto dijkstra = [&](int s) ->int{
        dis[s] = 0;
        pq.emplace(dis[s],s);
        while(!pq.empty()){
            auto [d,u] = pq.top(); pq.pop();
            if (dis[u] < d) continue;
            // v w kk
            for (auto it : G[u]) {
                if (dis[u]%it.second.second == 0) {
                    if (d + it.second.first < dis[it.first]){
                        dis[it.first] = d + it.second.first;
                        pq.emplace(dis[it.first],it.first);
                    }
                }else if (d + it.second.first + it.second.second - dis[u]%it.second.second < dis[it.first]) {
                    dis[it.first] = d + it.second.first + it.second.second - dis[u]%it.second.second;
                    pq.emplace(dis[it.first],it.first);
                }
            }
        }
        if (dis[y-1] != 1ll << 60) return dis[y-1];
        else return -1ll;
    };
    cout << dijkstra(x-1) << '\n';
    return 0;
}

 

###### tags: `演算法`
{%hackmd aPqG0f7uS3CSdeXvHSYQKQ %}