本篇标红的字段均是可以升级的经验条呦~OJ题来源洛谷OJ题名买礼物OJ题归属图论基础【最小生成树】解题算法kruskal算法kk算法经验总结用kurskal算法构造出来的生成树可能有若干个顶点有不连通的情况不影响他建树比如a-a a-a a-a|a-akruskal算法的关键变量cnt与节点n是有关系的cnt变量记录选的条数n是节点个数n - cnt 的差值就是构建出生成树的具体个数。#includeiostream #includealgorithm using namespace std; const int N 500 * 500 10; int pos; int a, n; int fa[N]; // 并查集 struct node { int x, y, z; }e[N]; int ret, cnt; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } bool cmp(node a, node b) { return a.z b.z; } void kk() { sort(e 1, e 1 pos, cmp); for (int i 1; i pos; i) { int x e[i].x, y e[i].y, z e[i].z; int fx find(x), fy find(y); if (fx ! fy) { cnt; ret z; fa[fx] fy; } } } int main() { cin a n; for (int i 1; i n; i) { for (int j 1; j n; j) { int k; cin k; if (i j || k a || k 0) continue; pos; e[pos].x i, e[pos].y j, e[pos].z k; } } // 并查集初始化 for (int i 1; i n; i) fa[i] i; kk(); // 求得ret/cnt cout ret (n - cnt) * a endl; return 0; }OJ题来源洛谷OJ题名繁忙的都市OJ题归属图论基础【最小生成树】解题算法kruskal算法kk算法此题有三个限制条件前两个条件翻译出来是要求是一棵生成树最后一个翻译出来是要是一颗瓶颈生成树。经验总结瓶颈生成树的概念在所有生成树中最大边权值最小的生成树。瓶颈生成树的定理最小生成树就是瓶颈生成树。最小生成树ret维护的是边权和最小瓶颈生成树ret维护的是 n - 1 条边中边权最大值#includeiostream #includealgorithm using namespace std; const int N 310, M 8010; int n, m; struct node { int x, y, z; }a[M]; int fa[N]; // 并查集维护已选的顶点 int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } int ret; // 维护 n - 1 条边中边权最大值 bool cmp(node a, node b) { return a.z b.z; } void kk() { sort(a 1, a 1 m, cmp); for (int i 1; i m; i) { int x a[i].x, y a[i].y, z a[i].z; int fx find(x), fy find(y); if (fx ! fy) { ret max(ret, z); fa[fx] fy; } } } int main() { cin n m; for (int i 1; i m; i) cin a[i].x a[i].y a[i].z; // 并查集初始化 for (int i 1; i n; i) fa[i] i; cout n - 1 ; kk(); cout ret endl; return 0; }OJ题来源洛谷OJ题名滑雪OJ题归属图论基础【最小生成树】解题算法dfs kruskal算法kk算法经验总结最小生成树在概念上是针对于无向图的但是这题向我们表明特殊情景下的有向图也是适用的这题的图是一个有向图但是题中提到的时间胶囊的概念其实功能就是回溯是的这样我们就可以把这个有向图可以看成可以递归的二叉树。此题的各个顶点之间不确定是不是连通的所以不是所有的边都需要记录我们只记录由1这个节点递归过程中可以经历的边对这些边进行排序、选边操作。此题kk算法的排序有改变滑雪滑雪排序的第一关键字就是高度由高到低高度一致时在按边权由小到大排序。#includeiostream #includealgorithm #includevector using namespace std; typedef long long LL; typedef pairint, int PII; const int N 1e5 10, M 2e6 10; int n, m; int h[N]; // 存该景点高度 vectorPII a[N]; // 存图 int fa[N]; // 并查集 int pos; // 在选择范围内的边数 struct node { int x, y, z; }e[M]; // 存储在选择范围内的边 LL cnt, ret; // 景点数 路径和 bool st[N]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void dfs(int u) { cnt; st[u] true; for (auto p : a[u]) { // 存储在选择范围内的边 int y p.first, z p.second; pos; e[pos].x u, e[pos].y y, e[pos].z z; if (!st[y]) dfs(y); } } bool cmp(node a, node b) { int ay a.y, by b.y; // 排序第一关键字高度第二关键字边权 if (h[ay] ! h[by]) return h[ay] h[by]; else return a.z b.z; } void kk() { sort(e 1, e 1 m, cmp); // 选边 for (int i 1; i pos; i) { int x e[i].x, y e[i].y, z e[i].z; int fx find(x), fy find(y); if (fx ! fy) { ret z; fa[fx] fy; } } } int main() { cin n m; for (int i 1; i n; i) cin h[i]; for (int i 1; i m; i) { int x, y, z; cin x y z; //判断哪些边可以存 if (h[x] h[y]) a[x].push_back({ y, z }); if (h[y] h[x]) a[y].push_back({ x, z }); } // 并查集初始化 for (int i 1; i n; i) fa[i] i; dfs(1); cout cnt ; kk(); cout ret endl; return 0; }感谢~
C++图论基础最小生成树经典OJ题流食般投喂
本篇标红的字段均是可以升级的经验条呦~OJ题来源洛谷OJ题名买礼物OJ题归属图论基础【最小生成树】解题算法kruskal算法kk算法经验总结用kurskal算法构造出来的生成树可能有若干个顶点有不连通的情况不影响他建树比如a-a a-a a-a|a-akruskal算法的关键变量cnt与节点n是有关系的cnt变量记录选的条数n是节点个数n - cnt 的差值就是构建出生成树的具体个数。#includeiostream #includealgorithm using namespace std; const int N 500 * 500 10; int pos; int a, n; int fa[N]; // 并查集 struct node { int x, y, z; }e[N]; int ret, cnt; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } bool cmp(node a, node b) { return a.z b.z; } void kk() { sort(e 1, e 1 pos, cmp); for (int i 1; i pos; i) { int x e[i].x, y e[i].y, z e[i].z; int fx find(x), fy find(y); if (fx ! fy) { cnt; ret z; fa[fx] fy; } } } int main() { cin a n; for (int i 1; i n; i) { for (int j 1; j n; j) { int k; cin k; if (i j || k a || k 0) continue; pos; e[pos].x i, e[pos].y j, e[pos].z k; } } // 并查集初始化 for (int i 1; i n; i) fa[i] i; kk(); // 求得ret/cnt cout ret (n - cnt) * a endl; return 0; }OJ题来源洛谷OJ题名繁忙的都市OJ题归属图论基础【最小生成树】解题算法kruskal算法kk算法此题有三个限制条件前两个条件翻译出来是要求是一棵生成树最后一个翻译出来是要是一颗瓶颈生成树。经验总结瓶颈生成树的概念在所有生成树中最大边权值最小的生成树。瓶颈生成树的定理最小生成树就是瓶颈生成树。最小生成树ret维护的是边权和最小瓶颈生成树ret维护的是 n - 1 条边中边权最大值#includeiostream #includealgorithm using namespace std; const int N 310, M 8010; int n, m; struct node { int x, y, z; }a[M]; int fa[N]; // 并查集维护已选的顶点 int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } int ret; // 维护 n - 1 条边中边权最大值 bool cmp(node a, node b) { return a.z b.z; } void kk() { sort(a 1, a 1 m, cmp); for (int i 1; i m; i) { int x a[i].x, y a[i].y, z a[i].z; int fx find(x), fy find(y); if (fx ! fy) { ret max(ret, z); fa[fx] fy; } } } int main() { cin n m; for (int i 1; i m; i) cin a[i].x a[i].y a[i].z; // 并查集初始化 for (int i 1; i n; i) fa[i] i; cout n - 1 ; kk(); cout ret endl; return 0; }OJ题来源洛谷OJ题名滑雪OJ题归属图论基础【最小生成树】解题算法dfs kruskal算法kk算法经验总结最小生成树在概念上是针对于无向图的但是这题向我们表明特殊情景下的有向图也是适用的这题的图是一个有向图但是题中提到的时间胶囊的概念其实功能就是回溯是的这样我们就可以把这个有向图可以看成可以递归的二叉树。此题的各个顶点之间不确定是不是连通的所以不是所有的边都需要记录我们只记录由1这个节点递归过程中可以经历的边对这些边进行排序、选边操作。此题kk算法的排序有改变滑雪滑雪排序的第一关键字就是高度由高到低高度一致时在按边权由小到大排序。#includeiostream #includealgorithm #includevector using namespace std; typedef long long LL; typedef pairint, int PII; const int N 1e5 10, M 2e6 10; int n, m; int h[N]; // 存该景点高度 vectorPII a[N]; // 存图 int fa[N]; // 并查集 int pos; // 在选择范围内的边数 struct node { int x, y, z; }e[M]; // 存储在选择范围内的边 LL cnt, ret; // 景点数 路径和 bool st[N]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void dfs(int u) { cnt; st[u] true; for (auto p : a[u]) { // 存储在选择范围内的边 int y p.first, z p.second; pos; e[pos].x u, e[pos].y y, e[pos].z z; if (!st[y]) dfs(y); } } bool cmp(node a, node b) { int ay a.y, by b.y; // 排序第一关键字高度第二关键字边权 if (h[ay] ! h[by]) return h[ay] h[by]; else return a.z b.z; } void kk() { sort(e 1, e 1 m, cmp); // 选边 for (int i 1; i pos; i) { int x e[i].x, y e[i].y, z e[i].z; int fx find(x), fy find(y); if (fx ! fy) { ret z; fa[fx] fy; } } } int main() { cin n m; for (int i 1; i n; i) cin h[i]; for (int i 1; i m; i) { int x, y, z; cin x y z; //判断哪些边可以存 if (h[x] h[y]) a[x].push_back({ y, z }); if (h[y] h[x]) a[y].push_back({ x, z }); } // 并查集初始化 for (int i 1; i n; i) fa[i] i; dfs(1); cout cnt ; kk(); cout ret endl; return 0; }感谢~
