題目描述
如題，給出一個(gè)無(wú)向圖喜爷，求出最小生成樹(shù)，如果該圖不連通萄唇，則輸出orz
輸入輸出格式
輸入格式：
第一行包含兩個(gè)整數(shù)N檩帐、M，表示該圖共有N個(gè)結(jié)點(diǎn)和M條無(wú)向邊穷绵。（N<=5000轿塔，M<=200000）
接下來(lái)M行每行包含三個(gè)整數(shù)Xi特愿、Yi仲墨、Zi勾缭，表示有一條長(zhǎng)度為Zi的無(wú)向邊連接結(jié)點(diǎn)Xi、Yi
輸出格式：
輸出包含一個(gè)數(shù)目养，即最小生成樹(shù)的各邊的長(zhǎng)度之和俩由；如果該圖不連通則輸出orz
輸入輸出樣例
輸入樣例#1：
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
輸出樣例#1：
7
1.Kruskal算法簡(jiǎn)介
Kruskal算法一般稱作克魯斯卡爾算法“┮希克魯斯卡爾算法是一種用來(lái)尋找最小生成樹(shù)的算法幻梯。在剩下的所有未選取的邊中，找最小邊努释，如果和已選取的邊構(gòu)成回路碘梢，則放棄，選取次小邊伐蒂。
2.Kruskal算法思想
先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)煞躬、而邊集為空的子圖，把子圖中各個(gè)頂點(diǎn)看成各棵樹(shù)上的根結(jié)點(diǎn)逸邦，之后恩沛，從網(wǎng)的邊集 E 中選取一條權(quán)值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹(shù)缕减，則將其加入子圖雷客，即把兩棵樹(shù)合成一棵樹(shù)，反之桥狡，若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹(shù)上搅裙，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之裹芝。依次類推呈宇，直到森林中只有一棵樹(shù)，也即子圖中含有 n-1 條邊為止局雄。
時(shí)間復(fù)雜度為為O(e^2), 使用并查集優(yōu)化后復(fù)雜度為 O（eloge）甥啄，與網(wǎng)中的邊數(shù)有關(guān)，適用于求邊稀疏的網(wǎng)的最小生成樹(shù)炬搭。
3.Kruskal算法解題過(guò)程
首先我們需要解決一個(gè)問(wèn)題蜈漓，不能構(gòu)成回路，這時(shí)宫盔，我們可以先使用并查集的思想融虽，先把每條邊存為獨(dú)立的根，然后灼芭，尋找最短邊權(quán)時(shí)有额，我們可將已經(jīng)找過(guò)的邊合并到集內(nèi)，防止構(gòu)成回路，選擇其他的次小邊巍佑。
接著就是Kruskal處理核心茴迁，我們需要先將邊進(jìn)行排序，這樣有利于后面選擇最小邊萤衰。
循環(huán)0-n次 且 i < n && nEdge != m - 1堕义，為什么要nEdge != m - 1呢？
這個(gè)意思就表達(dá)了這個(gè)圖是不連通的脆栋，也同樣等價(jià)于不存在最小生成樹(shù)倦卖。
接著，我們可以查找這兩邊的根椿争，如果他們的根節(jié)點(diǎn)都不一樣怕膛，就表示能夠增加這個(gè)邊權(quán)，它既是最小的秦踪，并且也不會(huì)構(gòu)成回路嘉竟。然后聲明一個(gè)記住最小邊權(quán)變量，最后輸出既完成本題目洋侨。
下面是具體的代碼實(shí)現(xiàn)
#include <cstdio>
#include <cstdlib>
#define MAXN 200000 + 10//對(duì)于100%的數(shù)據(jù)
using namespace std;
int par[MAXN], Rank[MAXN];//并查集 rank
typedef struct {
int a, b, price;
}Node;//結(jié)構(gòu)體儲(chǔ)存
Node a[MAXN];
int cmp(const void*a, const void *b) {
return ((Node*)a)->price - ((Node*)b)->price;//用于比較邊權(quán)
}
void Init(int n) {
for (int i = 0; i < n; i++) {
Rank[i] = 0;
par[i] = i;
}
}
int find(int x) {
int root = x;
while (root != par[root]) root = par[root];
while (x != root) {
int t = par[x];
par[x] = root;
x = t;
}
return root;
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (Rank[x] < Rank[y]) {
par[x] = y;
}
else {
par[y] = x;
if (Rank[x] == Rank[y]) Rank[x]++;
}
}
//n為邊的數(shù)量舍扰，m為村莊的數(shù)量
int Kruskal(int n, int m) {
int nEdge = 0, res = 0;
//將邊按照權(quán)值從小到大排序
qsort(a, n, sizeof(a[0]), cmp);
for (int i = 0; i < n && nEdge != m - 1; i++) {
//判斷當(dāng)前這條邊的兩個(gè)端點(diǎn)是否屬于同一棵樹(shù)
if (find(a[i].a) != find(a[i].b)) {
unite(a[i].a, a[i].b);
res += a[i].price;
nEdge++;
}
}
//如果加入邊的數(shù)量小于m - 1,則表明該無(wú)向圖不連通,等價(jià)于不存在最小生成樹(shù)
if (nEdge < m - 1) res = -1;
return res;
}
int main() {
int n, m, ans;
scanf("%d%d", &n, &m);
Init(n);
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].price);
//將村莊編號(hào)變?yōu)?~m-1（這個(gè)僅僅只是個(gè)人習(xí)慣，并非必要的）
a[i].a--;
a[i].b--;
}
int rets = Kruskal(m, n);//計(jì)算最小生成樹(shù)
//輸出結(jié)果
if (rets == -1)
printf("orz");
else printf("%d", rets);
return 0;
}
