前言(无关紧要的)本以为学完LCA之后开始学最短路就没有树的任何事了没想到今天上课真是天塌了(T_T)好的 废话不多说咱们切入正题。跨思春(Question)首先呢我们来学习一下什么是orz来 我们把o看作头r看作身体看作腿。……你好像发现了什么解题思路What is 最小生成树最小生成树的特点最小生成树包含了图中的所有顶点。它是一棵树因此对于含有n个顶点的图它有(n-1)条边。所有可能的生成树中最小生成树的边权重之和最小。最小生成树解题步骤把边权从小到大排序将n个点设置成单独的集合(并查集)从小到大循环边如果边的两端属于不同集合那就选中(选中就意味着要合并)重复3. 直到选出(n-1)条边代码如下#include bits/stdc.h // 万恶之源n-1 using namespace std; // 万恶之源n int n, m, ans; // n是点 m是边 ans是最小生成树元素之和 int x, y, z; // x是左节点 y是右节点 z是边(x-y)的权值 struct edge { // 没人知道edge是什么 int u, v, w;// u,v,w是为了为后文输入做铺垫, 表达了作者对最小生成树算法的喜爱与赞美之情。 }; // 哎呀呀 edge a[200005]; // a数组用来存储输入 bool cmp(edge a, edge b) { // -------------------------// return a.w b.w; // 结构体排序 ------- 步骤1.// } // -------------------------// int fa[200005]; int find(int x) { // 并查集查询 if (x fa[x]) return x; // 如果自己的father是自己那么找到根节点了 return fa[x] find(fa[x]);// 否则就一直找, 此处使用了路径压缩 } // -------------- 2. int main() { cin n m; for (int i 1; i m; i) { // 输入来了 cin x y z; a[i] {x, y, z}; } sort(a 1, a m 1, cmp); // 排序 for (int i 1; i n; i) { // 把所有的节点定义为自己的father fa[i] i; } int cnt 0; // cnt用来统计是否查找了(n-1)次 for (int i 1; i m; i) { // 遍历每一条边 int fu find(a[i].u); // LCA o(T_T)o int fv find(a[i].v); // LCA o(^v^)o if (fu ! fv) { // 如果祖先不一样那么便被选中了 fa[fu] fv; ans a[i].w; cnt; if (cnt n - 1) break; // ------------------ 3. } } // -------------- 4. if (cnt ! n - 1) cout orz; // 如果没有找到(n-1)条边, 那很遗憾了 else cout ans; // 最后输出 return 0; // 万恶之源inf } // 完结撒花❀ // *★,.*:.\(^v^)/*.:,.★* 。 // orz
