昨天： 圖論-最小生成樹<Dijkstra,Floyd>
以上是昨天的Blog，有需要者請先閱讀完以上再閱讀今天的Blog，
可能今天的有點亂，好好理理，認真看完相信你會懂得
然而，文中提到的所有的演算法在本人Blog中都會后期有講解，推薦Blog
分割線
第三天
引子：昨天我們簡單講了講最小生成樹<Dijkstra,Floyd>演算法，今天的課程就開始啦！
今天我們要講的是：最小生成樹
Top1：概念
最小生成樹，聽起來好像是樹呀，為什么會是圖論呢？其實，處理最小生成樹問題前給出的東西，就是一個圖，只不過進行操作后要求變成一個最小生成樹罷了，
那什么是最小生成樹呢？
我們把這個詞語拆開來看，
樹 ，我們都好理解，父親兒砸祖先啥的如果不知道的話......先百度完樹再來看吧 ，那么我們根據樹的特性可以得出一個結論：
最小生成樹是沒有環的
生成樹 ，就是一個點到另一個點的路徑是 唯一的 ，（可以通過樹的無環性質證明），也就是 一個用N-1條邊連接的樹，且所有點到其他點的路徑唯一
最小 代表最終生成樹的邊權和最小（不知道什么是邊權的到博主的Blog里面去看吧），
這里就有一個問題了：為什么會是N-1條邊呢，而不是N-2或者N+1條邊？
既然要把N個點用最少數量的邊（這里不是上面“最小”的定義）將所有點連接起來，（忽略邊權）上過小學的都知道，將兩個點連起來是要一條邊，三個點要兩條邊，哪里見過三個點用一條邊連起來的？用N條邊或N+1條邊（即上述例子的三條邊或四條邊），自然就會浪費邊了，
主要還是靠自己動手畫圖思考，
Top2：演算法-Kruskal
概念我們講完了，進入正題，
其實最小生成樹還有個演算法叫做Prim，Prim演算法和Kruskal演算法在于，一個在稀疏圖中更快，一個在稠密圖中更快，然而，Kruskal在比賽中會更好用，
那講了這么多，Kruskal到底怎么用呢？
我們都知道了樹沒有環，那么只需要每次取權值最小的邊，只要加入這條邊之后不行成環，就可以了，
有點像貪心，但是要判斷有沒有環，
怎么判斷有環沒環呢？
——并查集
所以代碼就很簡答啦！
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5000 + 10;
struct Line{
int x, y;
int dis;
bool operator < (const Line& next) const {
return dis > next.dis;
}
};
priority_queue<Line> line;
int n, m, now;
int fa[MAXN];
int ans;
inline int read(){
int f = 1, x = 0;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return f * x;
}
int find(int x){
if(fa[x] == x)return x;
return fa[x] = find(fa[x]);
}
int main(){
n = read(),m = read();
for(int i = 1;i <= m; i++){
int x,y,z;
x = read(),y = read(),z = read();
Line tot = {x,y,z};
line.push(tot);
}
for(int i = 1;i <= n; i++){
fa[i] = i;
}
while(!line.empty()){
Line tot = line.top();
line.pop();
int nx = tot.x, ny = tot.y;
if(find(nx) == find(ny)){
continue;
}
fa[find(nx)] = find(ny);
ans += tot.dis;
now++;
if(now == n - 1){
printf("%d",ans);
return 0;
}
}
puts("orz");
return 0;
}
至于Prim嗎......博主太菜，告辭！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/91715.html
標籤：C++
上一篇：奇怪的情況，我用delphi7和sql2005寫了個程式，長時間放置后，第一次讀不出資料，第二次才行，不知道什么情況？