最小生成樹(Minimum Spanning Tree)

(1)概念

我們知道，樹是有$n$個結點，$n?1$條邊的無向無環的連通圖。

一個連通圖的生成樹是一個極小的連通子圖，它包含圖中全部的$n$個頂點，但只有構成一棵樹的$n?1$條邊。

最小生成樹就是一個帶權圖，每個邊都有一個邊權，一顆生成樹的權值是該樹邊所有邊權的和，$MST$就是所有生成樹中最小的一個。

(2)Prim算法（遍歷點的算法）

普里姆算法在找最小生成樹時，將頂點分為兩類，一類是在查找的過程中已經包含在生成樹中的頂點（假設為 A 類），剩下的為不在生成樹中的（假設為 B 類）。

對于給定的連通網，起始狀態全部頂點都歸為 B 類。在找最小生成樹時，選定任意一個頂點作為起始點，并將之從 B 類移至 A 類；然后找出 B 類中到 A 類中的頂點之間權值最小的頂點，將之從 B 類移至 A 類，如此重復，直到 B 類中沒有頂點為止。所走過的頂點和邊就是該連通圖的最小生成樹。

int dis[N];
int mp[N][N];
bool vis[N];void work() {int n, m;cin >> n >> m;int ans = 0;memset(vis, 0, sizeof vis);memset(mp, 0x3f3f3f3f, sizeof mp);for (int i = 0; i < n; ++i) {int u, v, w;cin >> u >> v >> w;mp[u][v] = w;mp[v][u] = w;}for (int i = 0; i < n; ++i) {dis[i] = 0x3f3f3f3f;}dis[0] = 0;vis[0] = 1;for (int i = 1; i < n; ++i) {dis[i] = min(dis[i], mp[0][i]);}for (int i = 1; i < n; ++i) {//這里的外層循環是循環遍數，與i值無關double minn = 0x3f3f3f3f;int pos = -1;for (int j = 1; j < n; ++j) {//每次循環找出與已排聯通塊距離最近的點if (!vis[j] && minn > dis[j]) {pos = j;minn = dis[j];}}ans += minn;vis[pos] = 1;for (int j = 0; j < n; ++j) {//刷新未連接點的距離最小值dis[j] = min(dis[j], mp[pos][j]);}}cout << ans << '\n';
}

正確性顯然。

復雜度是$O(n^2)$級別的，但是我們可以使用堆優化降到$O(nlogn)$，之后講最短路的時候會講堆優化。

(3)Kruskal算法（遍歷邊的算法）

克魯斯卡爾算法（Kruskal）是一種使用貪婪方法的最小生成樹算法。 該算法初始將圖視為森林，圖中的每一個頂點視為一棵單獨的樹。 一棵樹只與它的鄰接頂點中權值最小且不違反最小生成樹屬性（不構成環）的樹之間建立連邊。

利用并查集可以快速實現查找兩個點是否已經連接

int n, m;
int f[105];
struct road {int a, b, v;
} arr[305];int find(int a) {if (f[a] == a)return a;elsereturn f[a] = find(f[a]);
}void join(int a, int b) {if (find(a) != find(b))f[find(a)] = find(b);
}bool cmp(road a, road b) {return a.v < b.v;
}void work() {cin >> n >> m;int a, b, c;for (int i = 1; i <= n; ++i) {f[i] = i;}int ans = 0;for (int i = 0; i < m; ++i) {cin >> arr[i].a >> arr[i].b >> arr[i].v;}sort(arr, arr + m, cmp);//先按路的權值排序，如果兩點的祖先不是一個就加上然后合并。for (int i = 0; i < m; ++i) {if (find(arr[i].a) != find(arr[i].b)) {ans += arr[i].v;join(arr[i].a, arr[i].b);}}cout << ans << '\n';return 0;
}

正確性證明：

給一帶權連通的樹一定會有至少一棵生成樹，那么這些生成樹中間必然會會存在至少一棵最小生成樹。

假設$T$是用$kruskal$求出來的最小生成樹，而$U$是這個圖的最小生成樹，要證$U=T$。
然而如果$T\ne U$，那么至少存在一條邊在$T$中，不在$U$中，假設存在$k$條邊存在$T$中不存在$U$中。
接下來進行$k$次變換：
每次將在$T$中不在$U$中的最小的邊$f$拿出來放到$U$中，那么$U$中必然形成一條唯一的環路，我們取出這個環路上最小的且不在$T$中的邊$e$放回到$T$中，這樣的邊$e$一定是存在的，因為之前的$T$不存在環路（如果$e$在$T$中那么就可能和$f$形成環路）。

現在證明$f$和$e$權值的關系：

假設$f<e$,那么后來形成的$U$是權值之和更小了，與$U$是最小生成樹矛盾。 實際上，不可能在$U$中拿到大于$f$的邊，因為把$f$拿走后，如果小于$f$的邊都不成立，至少$f$是一個符合條件的邊會被那回。

假設$f>e$,那么根據$kruskal$的做法，$e$是在$f$之前被取出來的邊但是被舍棄了，一定是因為$e$和比$e$小的邊形成了環路，而比$e$小的邊都是存在$U$中的，而$e$和這些邊并沒有形成環路，于假設矛盾。

于是$f$一定和$e$相等的，$k$次變換后，$T$和$U$的權值之和是相等的。

最小生成樹的值也是相等的。

復雜度是$O(nlogn)$級別的，一般有mst就用這個。

int f[N];
struct road {int a, b, v;
} arr[N];
int tot = 0;int find(int a) {if (f[a] == a)  return a;return f[a] = find(f[a]);
}void join(int a, int b) {if (find(a) != find(b)) f[find(a)] = find(b);
}bool cmp(road a, road b) {return a.v < b.v;
}void work() {int a, b;cin >> a >> b;for (int i = 1; i <= b; ++i) {f[i] = i;arr[i] = {0, i, a};}tot = b;for (int i = 1; i <= b; ++i) {for (int j = 1; j <= b; ++j) {int x; cin >> x;if (x == 0) continue;else arr[++tot] = {i, j, x};}}ll ans = 0;sort(arr + 1, arr + 1 + tot, cmp);for (int i = 1; i <= tot; ++i) {if (find(arr[i].a) != find(arr[i].b)) {ans += arr[i].v;join(arr[i].a, arr[i].b);b--;}if (b == 0) break;}cout << ans << '\n';
}