演算法與資料結構實驗題 10.23 寡人的難題
題目內容
★實驗任務
寡人心系天下為國為民，想要在歷史中留下點痕跡，就必須要讓國家強盛起來，正所謂想致富先修路，寡人覺得去修路，那些吃干飯的大臣給了寡人很多條要修的道路，奈何國庫空虛，寡人只能選擇其中一些道路，把重點城市連接在一起，并且這些道路的花費要最少，寡人決定讓你來接受這個任務，替寡人分憂，
★資料輸入
第一行有兩個正整數n，m，表示有n個城市（城市按照1到n編號），m條道路可選擇，
接下來有m行，每行有三個正整數u，v，c，分別表示這一條道路連通u和v且花費黃金c兩，
（1<=n<=50000,n-1<=m<=200000,1<=c<=10000）
★資料輸出
輸出能連通所有城市的道路的最小花費，
輸入示例
3 3
1 2 3
2 3 4
1 3 2
輸出示例
5
題目分析
把重點的城市鏈接在一起 -> 連接圖上所有的點
道路的花費最小 -> 總權和最小
題目看到這里, 題意其實很明顯了. 沒有什么別的東西, 就是要求給定的圖的最小生成樹.
選擇演算法
目前學習到的只有兩種演算法: Prim 和 Kruskal. 選擇哪種呢? 來看看區別
- Prim 演算法
這個演算法的基本思想是從小到大加入點.
任意選擇一個起點, 按照貪心的原則, 不斷的往圖中添加距離最小的一個點, 直到圖中有 n 個點.
不細說, 實作比 Kruskal 復雜. 這題我偷懶了, 主要談談本題用到的 Kruskal 演算法. ??
- Kruskal 演算法
這個演算法的基本思想是從小到大加入邊.
從權重最小的一條邊開始, 按照貪心的原則, 不斷的往圖中添加權重最小的邊，直到圖中有 n - 1 條邊.
本文使用的演算法是 Kruskal 演算法.
Kruskal 把所有的頂點以是否加入最小生成樹為依據分為兩個頂點集合.
生成演算法從權重最小的邊開始檢查:
如果這條邊不在最小生成樹當中.
就將這條邊加入到最小生成樹當中. 這使得每次加入的邊都是最優的, 或者說每次加入的邊都是未加入的邊當中最小的一條邊.
如果這條邊在最小生成樹當中.
則跳過該邊, 繼續檢查次小的邊.
直到最小生成樹中已經有 n 個頂點, 就退出回圈. 最小生成樹構建完畢.
在如圖所示的無向連通圖中, 應用 Kruskal 演算法求最小生成樹可以有如下程序:
Kruskal 演算法的實作方法
我們需要怎樣的資料結構來實作所需的操作呢? 要實作這個演算法, 我們首先要解決下面三個問題.
如何存放圖? 怎么每次都找到權重最小的邊? 怎樣知道這條邊是不是已經在當前的最小生成樹當中?
- 如何存放圖
因為求解最小生成樹的程序中, 并不涉及對某一條特定邊或特定點的查詢或是直接修改. 所以直接使用順序表存盤圖就ok了.
- 怎么找權重最小的邊.
線性遍歷, 排序, 最小堆... 都可解決這個問題. 同樣的, 最小生成樹中并不涉及到對邊集動態的查詢修改等操作. 又關注到題目給定的權重的資料范圍很小.
我們選擇簡單且快速的方法: 計數排序即可.
配合順序表存盤. 可以快速優雅地實作演算法的前期初始化作業.
- 怎么知道這條邊是不是已經在當前最小生成樹當中
再回顧下我們剛剛提到的演算法流程以及示例演示. 與其說我們關注某個點是否已經加入到當前的最小生成樹中, 我們也可以等效的說我們關注的是與這幾條邊相關的頂點是否已經加入到了最小生成樹之中.
合并-檢查-合并-檢查. 熟悉嗎? 我們有一個專門實作這個功能的資料結構. 并查集!
在 Kruskal 演算法中. 我們不難有以下結論:
-
檢查一條邊是否在最小生成樹中 == 這兩個點是否在最小生成樹的頂點集合中
-
加入一條邊 == 將相關的兩個點加入到頂點集合當中
這用并查集可以極其方便的實作.
代碼實作
了解完完整思路之后, 來看看代碼要怎么寫吧.
根據上述的思路. 我們先列出簡單的偽代碼.
int main(void)
{
int 總權值 = 0;
存盤圖;
for (e : 權重最小的邊)
{
嘗試合并 e 進 MST 中
{
成功: 總權值 += e 的權重;
失敗: 繼續回圈, 檢查下一條邊;
}
}
}
再將上述的討論兌現成具體的代碼.
有一點問題要額外注意一下.
在寫這份解題報告的時候, 題目的測驗資料是存在問題的.
題目給出的資料不一定是一個連通圖. 也就是說, 有的城市可能根本就走不到.
要補充一個回圈退出條件才可以 AC 本題. 即若所有邊已經遍歷完成, 則退出回圈
整合一下代碼
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
inline int read();
class DisjointSet
{
vector<int> _parent; // 存盤最小生成樹中各個頂點連接關系
vector<int> _size; // 頂點的子節點個數. 啟發式合并 unite() 用到的參考資料 (優化效率, 非必要代碼可以去掉).
public:
// 初始化并查集. _parent 列舉初始化. 函式 iota() 的意思是從 _parent 的首元素到末尾元素 按從 0, 1, 2, ..., n 的順序初始化.
// _size 全部置 1
DisjointSet(int s) : _parent(s), _size(s, 1) { iota(_parent.begin(), _parent.end(), 0); }
// 遞回查找目標節點. 順便壓縮下路徑.
int find(int x) { return _parent[x] == x ? x : _parent[x] = find(_parent[x]); }
// 合并 x <-- y. 回傳值為合并是否成功.
bool unite(int x, int y)
{
x = find(x), y = find(y);
if (x == y) return false; // 已經在一個集合內, 合并失敗.
if (_size[x] < _size[y])
swap(x, y); // 啟發式合并, 使得每次都是小的集合加入到大的集合中. (非必要代碼, 可洗掉)
// 合并
_parent[y] = x; // 修改根節點指向
_size[x] += _size[y]; // 更新合并后的子節點數量
return true;
}
};
struct Edge {int from, to;};
#define WEIGHT_MAX 10010
int main(void)
{
#ifdef LOCAL_COMPILE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
// 初始化.
// 存盤圖 & 按權重排序邊.
int n = read(); int m = read();
int u, v, w, max = 0; // 臨時存盤變數及輸入權重的最大值(作為 Kruskal 的退出條件).
vector<Edge> edgeSet[WEIGHT_MAX]; // 用計數排序的思想, 將邊的權重作為 edgeSet 的下標, 在輸入的程序中完成自然排序.
for (int i = 0; i < m; i++)
{
u = read(); v = read(); w = read(); // 讀入邊
edgeSet[w].push_back({u - 1, v - 1}); // 存盤邊
}
// Kruskal 演算法.
// 本題是有一個坑點在的, 題目給出的資料不一定是一個連通圖. 也就是說, 有的城市可能根本就走不到. 體現在代碼中多加一個回圈退出條件.
int ans = 0;
DisjointSet mst(n); // 并查集記錄已連接的頂點.
for (int i = 0, cnt = 1; cnt < n; i++) // 從權重為 0 的邊開始遍歷, 當已經加入 n - 1 或者已經遍歷了所有的邊了, 就退出回圈.
for (auto j : edgeSet[i]) // 遍歷權重為 i 的所有邊
if (mst.unite(j.from, j.to)) // 嘗試將邊 j 加入 MST. 若成功則更新答案, 若否繼續回圈.
{
ans += i;
cnt++;
}
cout << ans;
return 0;
}
inline int read()
{
int ret = 0, sign = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
sign = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
ret = (ret << 1) + (ret << 3) + (ch ^ 48);
ch = getchar();
}
return ret * sign;
}
參考資料 Reference
最小生成樹 - OI Wiki (oi-wiki.org)
并查集應用 - OI Wiki (oi-wiki.org)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/540032.html
標籤：其他