理論基礎：

例題：

卡碼網---53：尋寶

題目

題目描述

在世界的某個區域，有一些分散的神秘島嶼，每個島嶼上都有一種珍稀的資源或者寶藏。國王打算在這些島嶼上建公路，方便運輸。

不同島嶼之間，路途距離不同，國王希望你可以規劃建公路的方案，如何可以以最短的總公路距離將 所有島嶼聯通起來。?

給定一張地圖，其中包括了所有的島嶼，以及它們之間的距離。以最小化公路建設長度，確保可以鏈接到所有島嶼。

輸入描述

第一行包含兩個整數V 和 E，V代表頂點數，E代表邊數?。頂點編號是從1到V。例如：V=2，一個有兩個頂點，分別是1和2。

接下來共有 E 行，每行三個整數 v1，v2 和 val，v1 和 v2 為邊的起點和終點，val代表邊的權值。

輸出描述

輸出聯通所有島嶼的最小路徑總距離

筆記：

這道題的總體思路是：先將所有邊進行權值排序優先選擇權值小的邊，然后從權值最小的邊開始判斷該邊左右兩點是否為同一個祖先，如果為同一祖先那么聯通圖中就存在環，否則我們就將這兩點加入到聯通圖中，這里就用到了我們并查集的思路。然后我們將同意聯通圖中的帶權邊的權值加起來就是連接所有節點的最小連通子圖。

最小生成樹問題解決的都是求所給帶權有向圖中的所有節點的最小連通子圖，prim算法是從節點的角度出發，不斷選擇里最小生成樹最近的節點從而達到最小聯通子圖，而kruskal算法是從邊的角度出發，對邊的權值進行排序，優先選擇權值最小的邊加入到最小生成樹中，從而構成最小聯通子圖。

prim算法是將符合條件的點一個一個加入到最小生成樹中，kruskal算法是將符合條件的帶權邊一條一條的加入到最小生成樹中。kruskal算法是從所有帶權邊中尋找符合條件的邊加入到最小生成樹。

#include<bits/stdc++.h>
using namespace std;struct Edge{int l;int r;int val;
};bool s_rule(const Edge& a, const Edge& b){return a.val < b.val;
}vector<int> father;void init(int n){for(int i = 1; i <= n; i++){father[i] = i;}
}int find(int x){return x == father[x] ? x : father[x] = find(father[x]);
}void join(int u, int v){u = find(u);v = find(v);father[v] = u;
}int main(){int v,e;int res = 0;cin >> v >> e;father = vector<int>(v + 1, 0);vector<Edge> edges;while(e--){int v1, v2, val;cin >> v1 >> v2 >> val;edges.push_back({v1, v2, val});}sort(edges.begin(), edges.end(), s_rule);int n = edges.size();init(v);for(int i = 0; i < n; i++){if(find(edges[i].l) != find(edges[i].r)){join(edges[i].l, edges[i].r);res += edges[i].val;}}cout << res << endl;return 0;
}