上週末的藍橋杯省模擬賽時最後一題是一道最小生成樹的題目，因為恰好在慕課上剛看到這個地方，所以現學了 Prim 算法，解決了這個題目 (大概)，賽後就打算多琢磨琢磨這一類題目。題目鏈接
最小生成樹問題，是指給定無向圖 G=(V,E)，連接 G 中所有點，且邊集是 E 的子集的樹稱為 G 的生成樹 (Spanning Tree)，而權值最小的生成樹稱為最小生成樹 (Minimal Spanning Tree，MST)。
一、Kruskal 算法#
Kruskal 算法易於編寫，且效率很高
紫書 p356 描述如下：
Kruskal 算法的第一步是給所有邊按照從小到大的順序排列，這一步可以直接使用庫函數 qsort 或者 sort。接下來從小到大依次考察每條邊 (u, v)。
- 情況 1：u 和 v 在同一個連通分量中，那麼加入 (u, v) 後會形成環，因此不能選擇。
- 情況 2：如果 u 和 v 在不同的連通分量，那麼加入 (u, v) 一定是最優的。 為什麼呢？下面用反證法 —— 如果不加這條邊能得到一個最優解 T, 則 T+(u, v) 一定有且只有一個環，而且環中至少有一條邊 (u', v') 的權值大於或等於 (u, v) 的權值。刪除該邊後，得到的新樹 T' = T + (u, v) - (u', v') 不會比 T 更差。因此，加入 (u, v) 不會比不加入差。
下面是伪代码：
把所有邊(按權值)排序，記第i小的邊為e[i](1 <= i < m)
初始化MST為空
初始化連通分量，讓每個點自成一個獨立的連通分量
for(int i = 0; i < m; i++) {
if(e[i].u 和 e[i].v 不在同一個連通分量) {
把邊e[i]加入MST
合併e[i].u和e[i].v所在的連通分量
}
}
在上面的伪代码中，最關鍵的地方在於 “連通分量的查詢與合併” ：需要知道任意兩個點是否在同一連通分量中，還需要合併這兩個連通分量。
有一種簡潔高效的算法可以用來處理這個問題 ——並查集
此處指路大佬解釋：超有愛的並查集～
將每個連通分量看作一個集合，該集合包含了連通分量中的所有點。這些點兩兩相通，而具體的連通方式無關緊要。在圖中，每個點都恰好屬於一個連通分量，對應到集合表示中，即為每個元素恰好屬於一個集合。換句話說，圖的所有連通分量可以用若干個不相交集合來表示。
奉上自己的並查集板子
#include <iostream>
using namespace std;
#define div 1000000007
typedef long long ll;
const int maxn = 1001;
int fa[maxn];//
inline void init(int n) {
for (int i = 1; i <= n; i++)
fa[i] = i;
}
int find(int x) {//查詢+路徑壓縮 把沿途的每個節點的父節點都設為根節點
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
inline void merge(int i, int j) {
fa[find(i)] = find(j);//前者的父節點設為後者
}
有了並查集之後，Kruskal 算法的完整代碼便不難給出。假設第 i 條邊的兩個端點序號和權值分別保存在 u [i]，v [i] 和 w [i] 中，而排序後第 i 小的邊的序號保存在 r [i] 中 (間接排序，即排序的關鍵字是對象的 “代號”，而不是對象本身),p 為並查集
完整代碼：#
int cmp(const int i, const int j) { return w[i] < w[j]; } //間接排序函數
int find(int x) { return p[x] == x ? x : p[x] = find(p[x])} //並查集的find
int Kruskal() {
int ans = 0;
for(int i = 0; i < n; i++) p[i] = i; //初始化並查集
for(int i = 0; i < m; i++) r[i] = i;
sort(r,r+m,cmp);
for(int i = 0; i < m; i++) {
int e = r[i];
int x = find(u[e]);//找出一個端點所在集合編號
int y = find(v[e]);//找出另一個端點所在集合編號
if(x != y) { //若在不同集合，合併
ans += w[e];
p[x] = y;
}
}
return ans;
}
練習題：#
題號 | 題目名稱 (英文)| 備註 |
|--|--|--|--|
hdu1863| 畅通工程 | 最小生成樹 板子題
hdu1879| 继续畅通工程 | 最小生成樹 板子題
hdu1875| 畅通工程再续 | 最小生成樹 板子題
洛谷 P3366| 【模板】最小生成樹 | 最小生成樹 板子題
1. hdu1863 畅通工程#
Problem Description
省政府 “畅通工程” 的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。
Input
测试输入包含若干测试用例。每个测试用例的第 1 行给出评估的道路条数 N、村庄数目 M (< 100)；随后的 N
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从 1 到 M 编号。当 N 为 0 时，全部输入结束，相应的结果不要输出。
Output
对每个测试用例，在 1 行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出 “?”。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 105;
int N,M,cnt;
int u[maxn],v[maxn],w[maxn];
int r[maxn],fa[maxn];
bool cmp(const int r1, const int r2) {
return w[r1] < w[r2];
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int Kruskal() {
int ans = 0;
for(int i = 0; i < M; i++) fa[i] = i;//初始化并查集，让每个点自成一个连通分量
for(int i = 0; i < N; i++) r[i] = i;//存储边序号
sort(r, r+N, cmp);//将边从小到大按权值排序
for(int i = 0; i < N; i++) {
int e = r[i];
int x = find(u[e]);
int y = find(v[e]);
if(x != y) {
ans += w[e];
cnt++;
fa[x] = y;
}
}
return ans;
}
int main() {
while(cin >> N >> M) {
cnt = 0;
if(N == 0) break;
for(int i = 0; i < N; i++) {
cin >> u[i] >> v[i] >> w[i];
}
int ans = Kruskal();
if(cnt != M-1) cout << "?" << endl;
else cout << ans << endl;
}
return 0;
}
2.hdu1879 继续畅通工程#
這題相比上題來說，就將已經建好的道路花費置為 0 即可，同時注意本題輸入輸出好像都不能用 cincout, 會超時。
Problem Description
省政府 “畅通工程” 的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。
Input
测试输入包含若干测试用例。每个测试用例的第 1 行给出村庄数目 N (1< N < 100)；随后的 N (N-1)/2 行对应村庄间道路的成本及修建状态，每行给 4 个正整数，分别是两个村庄的编号（从 1 编号到 N），此两村庄间道路的成本，以及修建状态：1 表示已建，0 表示未建。
当 N 为 0 时输入结束。
Output
每个测试用例的输出占一行，输出全省畅通需要的最低成本。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 5008;
int fa[101];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
struct Edge {
public:
int u, v, w;
bool operator<(const Edge &a)const{
return w < a.w;
}
}E[maxn];
int main() {
int N;
while(scanf("%d", &N) != EOF) {
int ans = 0;
if(N == 0) break;
int M = N*(N-1)/2;
for(int i = 1; i <= M; ++i) {
int flag;
scanf("%d%d%d%d", &E[i].u, &E[i].v, &E[i].w, &flag);
if(flag) E[i].w = 0;
}
for(int i = 1; i <= N; ++i) fa[i] = i;//初始化并查集，让每个点自成一个连通分量
sort(E+1,E+1+M);//将边从小到大按权值排序
for(int i = 1; i <= M; ++i) {
int x = find(E[i].u);
int y = find(E[i].v);
if(x != y) {
fa[x] = y;
ans += E[i].w;
}
}
printf("%d\n",ans);
}
return 0;
}
3.hdu1875 畅通工程再续#
先輸入所有頂點，再判斷每兩個頂點是否可以構成合適的邊
Problem Description
相信大家都聽說一個 “百島湖” 的地方吧，百島湖的居民生活在不同的小島中，當他們想去其他的小島時都要通過划小船來實現。現在政府決定大力發展百島湖，發展首先要解決的問題當然是交通問題，政府決定實現百島湖的全暢通！經過考察小組 RPRush 對百島湖的情況充分了解後，決定在符合條件的小島間建上橋，所謂符合條件，就是 2 個小島之間的距離不能小於 10 米，也不能大於 1000 米。當然，為了節省資金，只要求實現任意 2 個小島之間有路通即可。其中橋的價格為 100 元 / 米。
Input
輸入包括多組數據。輸入首先包括一個整數 T (T <= 200)，代表有 T 組數據。
每組數據首先是一個整數 C (C <= 100)，代表小島的個數，接下來是 C 組坐標，代表每個小島的坐標，這些坐標都是 0 <= x, y <= 1000 的整數。
Output
每組輸入數據輸出一行，代表建橋的最小花費，結果保留一位小數。如果無法實現工程以達到全部暢通，輸出”oh!”.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 5008;
typedef long long ll;
struct Point {
int x,y;
} V[101];
struct Edge {
public:
int u, v;
double w;
bool operator<(const Edge &a)const{
return w < a.w;
}
}E[maxn];
int fa[105];
int find(int x) {
return fa[x] == -1 ? x : fa[x] = find(fa[x]);
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
int N;
scanf("%d", &N);
for(int i = 0; i < N; ++i) {
scanf("%d%d", &V[i].x, &V[i].y);
}
int k = 0;
for(int i = 0; i < N-1; ++i) {
for(int j = i+1; j < N; ++j) {
double d = sqrt( (V[i].x-V[j].x)*(V[i].x-V[j].x) +
(V[i].y-V[j].y)*(V[i].y-V[j].y) );
if (d <= 1000 && d >= 10) {
E[k].u = i;
E[k].v = j;
E[k].w = d*100;
k++;
}
}
}
for(int i = 0; i < N; ++i) fa[i] = -1;//初始化并查集，让每个点自成一个连通分量
sort(E,E+k);//将边从小到大按权值排序
double ans = 0;
int cnt = 0;
for(int i = 0; i < k; ++i) {
int x = find(E[i].u);
int y = find(E[i].v);
if(x != y) {
fa[x] = y;
ans += E[i].w;
cnt++;
}
}
if (cnt == N-1) printf("%.1f\n",ans);
else printf("oh!\n");
}
return 0;
}
4.洛谷 P3366【模板】最小生成树 #
板子題
#include <iostream>
#include <algorithm>
using namespace std;
const int maxm = 200000;
int fa[5005];//最大頂點數5000
int N,M,cnt;//頂點數 邊數
struct edge {
int u,v,w;
bool operator<(const edge& a) const {
return w < a.w;
}
} E[maxm];//最大邊數maxn
int find(int x) {
return fa[x] == -1 ? x : fa[x] = find(fa[x]);
}
int Kruskal() {
for(int i = 0; i < N; ++i) fa[i] = -1;
int ans = 0;
sort(E,E+M);
for(int i = 0; i < M; ++i) {
int x = find(E[i].u);
int y = find(E[i].v);
if(x != y) {
fa[x] = y;
ans += E[i].w;
cnt++;
}
}
if(cnt == N-1) return ans;
else return -1;
}
int main() {
scanf("%d%d", &N, &M);
for(int i = 0; i < M; ++i) {
scanf("%d%d%d", &E[i].u, &E[i].v,&E[i].w);
}
int ans = Kruskal();
if(ans == -1) printf("orz\n");
else printf("%d\n",ans);
return 0;
}
二、Prim 算法#
來自陳越姥姥的數據結構
Prim 算法基本思路 —— 從一個根節點開始，讓一棵小樹長大。與 Dijkstra 算法相近。
Dijkstra 算法伪代码：
void Dijkstra(Vertex s) {
while(1) {
V = 未收錄頂點中dist最小者
if (這樣的V不存在)
break;
collected[V] = true;//將V收錄
for(V的每個鄰接點W) {
if(collected[W] == false && dist[V] + E(V,W) < dist[W]) {
dist[W] = dist[V]+E<V,W>;
path[W] = V;
}
}
}
Prim 算法伪代码：
void Prim(Vertex s) {
while(1) {
V = 未收錄頂點中dist最小者
if (這樣的V不存在)
break;
將V收錄進MST
for(V的每個鄰接點W) {
if(W未被收錄 && E(V,W) < dist[W]) {
dist[W] = E<V,W>;
parent[W] = V;
}
}
}
Prim 算法完整代碼#
double edge[maxn][maxn];//存邊的權值~
int vis[maxn];//該點是否已訪問過
double dist[maxn];
double ans;
double Prim() {
for(int i = 2; i <= n; i++) {
dist[i] = edge[1][i];//初始化dist為根結點1到所有點的距離
}
vis[1] = 1;////收錄初始點1 vis[i] == 0表示還未被收錄
for(int i = 2; i <= n; i++) {
int min = INF;
int v = -1;
for(int j = 2; j <= n; j++) {//找v————未收錄頂點中dist最小者
if(!vis[j] && dist[j] < min) {
min = dist[j];
v = j;
}
}
if(v != -1) {//找到了v~收入MST
vis[v] = 1;
ans += dist[v];
for(int j = 2;j <= n; j++) {//更新距離dist
if(!vis[j] && edge[v][j] < dist[j]) {//當這點未被訪問且到任意一點的距離比現在到樹的距離小就更新
dist[j] = edge[v][j];
}
}
}
}
return ans;
}