# 最小生成樹mst

* n個點，剛好有n-1條邊的就是樹（無向）
* 求一個有權重的圖中權重最小的樹的路徑
* 皆可以有負權重
* 也可以算最大生成樹
* 邊較多的圖：prim, 邊較少的圖：kruskal

prim
---

* 設s為root, $dis[v]$代表s到v的最點距離，$weight[a][b]$為a到b的權重，$done[v]=1$代表點v已走過, $parent[v]$是v的父節點
* $dis[s]=0$，其餘為無限大
* done設為0
* **步驟：**
1. 從沒走過的點中，找一個點x其$dis[x]$最小的，設done[x]=1，所以一開始x就是起點s
* 用priority_queue找dis[x]最小的，每次找最小又還沒走過的點，所以每次push{dis[u], u}，pop要檢查done[x]是否為1
2. 對於每個x連到的點y（如果已經做過done[y]==1就跳過，因為不能有環），做$dis[y]=min(dis[y], weight[x][y])$
3. 重複 1.
* $O(ElogV)$

#include <bits/stdc++.h>
#define EB emplace_back
#define vci vector<int>
#define PII pair<int,int>
#define F first
#define S second
#define rep(a,b) for(int i=a;i<b;++i)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
#define LL long long

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, u, v, w;
    cin>>n>>m;
    vector<vector<PII>> gh(n, vector<PII>());
    rep(0,m){
        cin>>u>>v>>w;
        gh[u].EB(make_pair(v, w));
        gh[v].EB(make_pair(u, w));
    //doesn't matter if there's multiple line between two nodes, the algorithm will take the least one
    }

    //init
    vector<int> done(n, 0);
    vector<int> parent(n);
    vector<int> dis(n, INT_MAX);
    dis[0]=0; //default dis[s] is 0
    
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({dis[0], 0});
    
    while(!pq.empty()){
        
        PII x=pq.top();
        pq.pop();
        if(done[x.S]) continue;
        done[x.S]=1;
        
        for(auto a:gh[x.S]){
            
            if(done[a.F]) continue; //need to do this
            if(a.S<dis[a.F]){
                dis[a.F]=a.S;
                parent[a.F]=x.S;
                pq.push({dis[a.F], a.F});
            }
            
        }
    }
    
    int sum=0, flag=0;
    rep(0,n){
        if(!done[i]){
            cout << -1 << NL;
            flag=1;
            break;
        }
        sum+=dis[i];
    }
    if(!flag) cout << sum << NL;
}

kruskal
---

1. 對各邊權重做排序
2. 從小到大選擇，如果不會形成迴圈就放進最小生成樹集合中，反之就忽略
* 用並查集判斷是否為迴圈
3. 如果最後邊數不到n-1就不可能組成樹
* $O(ElogE)$ or $O(VlogV)$ ?

#include <bits/stdc++.h>
#define EB emplace_back
#define vci vector<int>
#define PII pair<int,int>
#define F first
#define S second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
#define LL long long

using namespace std;

int p[10010];

int fd(int x){
    if(p[x]==x) return x;
    return fd(p[x]);
}

bool un(int a, int b){
    int f1=fd(a), f2=fd(b);
    if(f1==f2) return false;
    p[f2]=f1;
    return true;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, u, v, w;
    cin>>n>>m;
    vector<pair<int, pair<int,int>>> gh(n, pair<int, pair<int,int>>());
    //pair: {weight, {node1, node2}}

    rep(i,0,m){
        cin>>u>>v>>w;
        gh.EB(make_pair(w, make_pair(u, v)));
    }
    sort(ALL(gh));

    //init
    rep(i, 0, n) p[i]=i;

    LL cost=0, edge=0;
    for(auto v:gh){
        if(un(v.S.F, v.S.S)){
            edge++;
            cost+=v.F;
        }
    }

    if(edge<n-1) cout << -1 << NL;
    else cout << cost << NL;
}