重庆网站建设的意义,微信小程序后端开发教程,自己做网站后台,网页设计师资格证查询官网图论——最小生成树
A wise man changes his mind, a fool never will
生成树 一个连通图的生成树是一个极小的连通子图#xff0c;它包含图中全部的n个顶点#xff0c;但只有构成一棵树的n-1条边。 最小生成树 在这些边中选择N-1条出来#xff0c;连接所有的N个点。这N-1…图论——最小生成树
A wise man changes his mind, a fool never will
生成树 一个连通图的生成树是一个极小的连通子图它包含图中全部的n个顶点但只有构成一棵树的n-1条边。 最小生成树 在这些边中选择N-1条出来连接所有的N个点。这N-1条边的边权之和是所有方案中最小的。 Prim算法(一般用于稠密图——邻接矩阵)
思想(贪心)
每次将离连通部分的最近的点和点对应的边加入的连通部分连通部分逐渐扩大最后将整个图连通起来并且边长之和最小。
代码 输入格式 第一行包含两个整数 n 和 m。 接下来 m 行每行包含三个整数 u,v,w,表示点 u 和点 v 之间存在一条权值为 w的边。 输出格式 共一行若存在最小生成树则输出一个整数表示最小生成树的树边权重之和如果最小生成树不存在则输出 impossible。 #include iostream
#include cstring
#include algorithmusing namespace std;const int N 505, INF 0x3f3f3f3f;int g[N][N], dist[N];
int n;
bool st[N];int prim() {memset(dist, 0x3f, sizeof dist);int res 0;for (int i 0; i n; i ) {int t -1;for (int j 1; j n; j )if (!st[j] (t -1 || dist[t] dist[j]))t j;if (i dist[t] INF) return INF;st[t] true;if (i) res dist[t];for (int j 1; j n; j ) dist[j] min(dist[j], g[t][j]);}return res;
}int main() {int m;cin n m;memset(g, 0x3f, sizeof g);while (m --) {int a, b, c;cin a b c;g[a][b] g[b][a] min(g[a][b], c);}int t prim();if (t INF) cout impossible endl;else cout t endl;return 0;
}Kruskal 算法(一般用于稀疏图——邻接表)
思想
将所有边按照权值的大小进行升序排序然后从小到大一一判断。如果这个边与之前选择的所有边不会组成回路(并查集)就选择这条边反之舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。
代码 输入格式 第一行包含两个整数 n 和 m。 接下来 m 行每行包含三个整数 u,v,w表示点 u和点 v 之间存在一条权值为 w的边。 输出格式 共一行若存在最小生成树则输出一个整数表示最小生成树的树边权重之和如果最小生成树不存在则输出 impossible。 数据范围 1 n 1 0 5 1n10^5 1n105 1 m 2 ∗ 1 0 5 1m2*10^5 1m2∗105 图中涉及边的边权的绝对值均不超过 1000。 输入样例 4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4输出样例 6#include cstring
#include iostream
#include algorithmusing namespace std;const int N 1e5 10, INF 0x3f3f3f3f;struct node {int a, b, w;bool operator (node b)const {return w b.w;}
}e[N * 2];int p[N];int find(int x) {if (p[x] ! x)p[x] find(p[x]);return p[x];
}int n, m;int kruskal() {sort(e, e m);for (int i 1; i n; i ) p[i] i;int res 0, cnt 0;for (int i 0; i m; i ) {int a e[i].a, b e[i].b, w e[i].w;a find(a), b find(b);if (a ! find(b)){p[a] p[b]; cnt;res w;}}if (cnt n - 1) return INF;return res;
}int main() {cin n m;for (int i 0; i m; i ) {int a, b, w;cin a b w;e[i] {a, b, w};}int t kruskal();if (t INF) cout impossible endl;else cout t endl;return 0;
}
