赞
踩
目录:
如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz
。
输入格式:
第一行包含两个整数 N, M,表示该图共有 N 个结点和 M 条无向边。
接下来 M 行每行包含三个整数 Xi, Yi, Zi,表示有一条长度为 Zi 的无向边连接结点 Xi, Yi。
输出格式:
如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz
。
将所有的边按权值的大小从小到大进行排序,选取权值最小的边,回贴到图中并判断是否形成了环,若形成了环,则丢弃该边,继续下一条边的回贴,若没有形成环,则递归调用,继续下条边的判断。此时的判断有没有形成环,可以用有没有公共祖先进行判断,若存在公共祖先,则会形成环,否则不会,详情见代码。
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 5e5 + 10;
- const int maxv = 2e5 + 10;
- int n, m, ans, f[maxv];
- //因为该图为无向图,故存储时需要将数组长度扩大一倍
- struct edge{
- int u, v, w;
- }g[maxn];
-
- bool cmp(edge a,edge b) {
- return a.w < b.w;
- }
-
- int find(int a) {
- if (f[a] == a)
- return a;
- return f[a] = find(f[a]);
- }
-
- void construct() {
- int cnt = 0;
- for (int i = 1; i <= n; i++)
- f[i] = i;
- for (int i = 1; i <= m; i++) {
- int fx = find(g[i].u);
- int fy = find(g[i].v);
- //该步骤是为了判断是否形成了环
- if (fy != fx) {
- f[fx] = fy;
- ans += g[i].w;
- cnt++;
- }
- if (cnt == n - 1) {
- printf("%d", ans);
- break;
- }
- }
- if(cnt != n - 1)
- printf("orz");
- }
-
- int main() {
- scanf("%d %d", &n, &m);
- for (int i = 1; i <= m; i++)
- scanf("%d %d %d", &g[i].u, &g[i].v, &g[i].w);
- sort(g + 1, g + 1 + m, cmp);
- construct();
- return 0;
- }
首先从某个点出发,找到与之相连的最小权值的边,并将其回贴到图中,然后在此时的最小生成树中,找到某点与(还未加入最小生成树中的某点)形成的最小权值的边,并将其回贴到图中,如此递归形成最后的结果,详情见代码。
- #include<bits/stdc++.h>
- using namespace std;
- const int INF = 1e9 + 10;
- const int maxn = 5010;
- const int maxm = 2e5 + 10;
-
- struct edge{
- int v, w, next;
- }e[maxm * 2];
- //cnt表示有向边的条数
- //tot表示已连接的最小生成树的边
- //now代表此时准备连接哪个点
- //ans表示结果
- int cnt, n, m, tot, now = 1, ans;
- //head表示某点作为前驱节点时的编号
- //dis表示已经加入最小生成树的点到没有加入的点的最小距离
- //vis判断某个点是否已经加入最小生成树
- int head[maxn], dis[maxn], vis[maxn];
-
- void add(int u, int v, int w) {
- e[++cnt].v = v;
- e[cnt].w = w;
- e[cnt].next = head[u];
- head[u] = cnt;
- }
-
- void prim() {
- for(int i = 2; i <= n; ++i)
- dis[i] = INF;
- //注意重边
- //找出所有与1相连的点,记录两点间的最短距离
- for(int i = head[1]; i; i = e[i].next)
- dis[e[i].v] = min(dis[e[i].v], e[i].w);
- //最小生成树边数等于点数 - 1
- while(++tot < n) {
- int minn = INF;
- //标记走过的点
- vis[now] = 1;
- int t = now;
- //枚举每一个没有使用的点
- //找出最小值作为新边
- for(int i = 1; i <= n; ++i)
- if(!vis[i] && minn > dis[i]) {
- minn = dis[i];
- now = i;
- }
- //如果最新的结点未被修改,则无法形成最小生成树
- //故该图不连通,则需输出orz
- if(now == t) {
- printf("orz");
- return;
- }
- ans += minn;
- //枚举now的所有连边,更新dis数组
- for(int i = head[now]; i; i = e[i].next) {
- int v = e[i].v;
- if(dis[v] > e[i].w && !vis[v])
- dis[v] = e[i].w;
- }
- }
- printf("%d", ans);
- }
-
- int main() {
- scanf("%d %d", &n, &m);
- int u, v, w;
- for(int i = 1; i <= m; ++i) {
- scanf("%d %d %d", &u, &v, &w);
- //该图为无向图
- //故需要当作两条边加入结构体中
- add(u, v, w);
- add(v, u, w);
- }
- prim();
- return 0;
- }
输入:
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出:
7
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。