互联网定制产品网站,做图素材网站,网络推广软文,城乡规划师证报考条件【模板】最小生成树
题目描述
如题#xff0c;给出一个无向图#xff0c;求出最小生成树#xff0c;如果该图不连通#xff0c;则输出 orz。
输入格式
第一行包含两个整数 N , M N,M N,M#xff0c;表示该图共有 N N N 个结点和 M M M 条无向边。
接下来 M M M 行…【模板】最小生成树
题目描述
如题给出一个无向图求出最小生成树如果该图不连通则输出 orz。
输入格式
第一行包含两个整数 N , M N,M N,M表示该图共有 N N N 个结点和 M M M 条无向边。
接下来 M M M 行每行包含三个整数 X i , Y i , Z i X_i,Y_i,Z_i Xi,Yi,Zi表示有一条长度为 Z i Z_i Zi 的无向边连接结点 X i , Y i X_i,Y_i Xi,Yi。
输出格式
如果该图连通则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。
样例 #1
样例输入 #1
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3样例输出 #1
7提示
数据规模
对于 20 % 20\% 20% 的数据 N ≤ 5 N\le 5 N≤5 M ≤ 20 M\le 20 M≤20。
对于 40 % 40\% 40% 的数据 N ≤ 50 N\le 50 N≤50 M ≤ 2500 M\le 2500 M≤2500。
对于 70 % 70\% 70% 的数据 N ≤ 500 N\le 500 N≤500 M ≤ 1 0 4 M\le 10^4 M≤104。
对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 5000 1\le N\le 5000 1≤N≤5000 1 ≤ M ≤ 2 × 1 0 5 1\le M\le 2\times 10^5 1≤M≤2×105 1 ≤ Z i ≤ 1 0 4 1\le Z_i \le 10^4 1≤Zi≤104。
样例解释 所以最小生成树的总边权为 2 2 3 7 2237 2237。
代码
#include stdio.h
#include stdlib.h
#define MAXN 300000
#define MAXM 300000
typedef struct // 定义边的结构体
{int u, v, w;
}Edge;
Edge edges[MAXM]; // 存储所有的边
int pa[MAXN]; // 并查集数组用于判断两个节点是否在同一棵树中
int N, M; // N是节点数M是边数
int cmp(Edge a, Edge b); // 边的比较函数按照边的权重从小到大排序
int find(int x); // 并查集的查找函数用于查找节点x的根节点
int kruskal(); // Kruskal算法函数int main(int argc, char *argv[])
{int i;scanf(%d %d, N, M); // 读取节点数和边数for (i 0; i M; i){scanf(%d %d %d, edges[i].u, edges[i].v, edges[i].w);}int res kruskal(); // 调用Kruskal算法计算最小生成树的权重if (res -1) // 如果图不连通{printf(orz\n);}else{printf(%d\n, res);}return 0;
}int cmp(Edge a, Edge b) // 边的比较函数按照边的权重从小到大排序
{return (a.w - b.w);
}int find(int x) // 并查集的查找函数用于查找节点x的根节点
{while (pa[x] ! x){x pa[x];}return x;
}int kruskal() // Kruskal算法函数
{int i, j;for (i 0; i M; i) // 将所有的边按照从小到大排序{for (j i 1; j M; j){if (cmp(edges[i], edges[j]) 0){Edge temp edges[i];edges[i] edges[j];edges[j] temp;}}}for (i 1; i N; i) // 初始化并查集{pa[i] i;}int res 0; // 存储最小生成树的权重int cnt 0; // 存储当前已经选择的边的数量for (i 0; i M; i) // 遍历所有的边{int u find(edges[i].u); // 边的一个节点int v find(edges[i].v); // 边的另一个节点// 如果两个节点不在同一棵树中说明这条边可以添加到最小生成树中if (u ! v){res edges[i].w; // 更新最小生成树的权重pa[u] v; // 合并两棵树cnt; // 更新已经选择的边的数量}}if (cnt ! N - 1) // 如果选择边的数量小于N - 1说明图不连通{return -1;}return res; // 返回最小生成树的权重
}
