图论-最小生成树<Kruskal>

昨天： __[图论-最短路<Dijkstra,Floyd>](https://www.luogu.org/blog/37682/tu-lun-zui-xiao-sheng-cheng-shu-dijkstrafloyd)__ 以上是昨天的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; } ```