最小生成树

news/2024/10/31 5:27:25/

1:什么是最小生成树?

最小生成树是一个无向连通图的生成树,它的所有边的权值之和最小。也就是说,最小生成树是一棵权值最小的连通子图,其中包含了原图中的所有节点,但只保留了一部分边。最小生成树通常用于在一个图中寻找一个最小的连通子图,以便在资源有限的情况下,尽可能地覆盖原图中的所有节点。最小生成树可以用多种算法来求解,其中最常用的算法是Kruskal算法和Prim算法。

2:Kruskal算法和Prim算法

Kruskal算法:

Kruskal算法是一种基于贪心算法的最小生成树算法。它的实现方式是将所有边按照权值从小到大排序,然后依次加入生成树中,如果加入某条边后会形成环,则不加入该边。这个过程中,使用并查集来维护连通性。

Kruskal算法的时间复杂度为O(ElogE),其中E为边的数量。Kruskal算法适用于稀疏图,即边的数量相对于节点数量较少的图。

Prim算法:

Prim算法也是一种基于贪心算法的最小生成树算法。它的实现方式是从一个节点开始,依次加入与该节点相邻的边中权值最小的边,然后再从已加入的节点中选择一个与未加入节点相邻的权值最小的边加入生成树中。这个过程中,使用优先队列来维护边的权值。

Prim算法的时间复杂度为O(ElogV),其中E为边的数量,V为节点数量。Prim算法适用于稠密图,即边的数量相对于节点数量较多的图。

总之,Kruskal算法适用于稀疏图,Prim算法适用于稠密图。两种算法的时间复杂度都较为优秀,都可以在较短的时间内求解出最小生成树。

7-22 畅通工程之最低成本建设问题(Prim)

某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城镇间都可以实现快速交通(但不一定有直接的快速道路相连,只要互相间接通过快速路可达即可)。现得到城镇道路统计表,表中列出了有可能建设成快速路的若干条道路的成本,求畅通工程需要的最低成本。

输入格式:

输入的第一行给出城镇数目N (1<N≤1000)和候选道路数目M≤3N;随后的M行,每行给出3个正整数,分别是该条道路直接连通的两个城镇的编号(从1编号到N)以及该道路改建的预算成本。

输出格式:

输出畅通工程需要的最低成本。如果输入数据不足以保证畅通,则输出“Impossible”。

输入样例1:

6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

输出样例1:

12

输入样例2:

5 4
1 2 1
2 3 2
3 1 3
4 5 4

输出样例2:

Impossible

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int  G[1002][1002];
int *d;  //用来记录顶点与城镇间的最小花费
bool *visit;
int inf = 0xfffffff;
int ans, n,m;void Init()
{d = new int[n + 1];visit = new bool[n + 1];fill(d, d + n + 1,inf);fill(visit, visit + n + 1, false);  fill(G[0], G[0] + 1002 * 1002, inf);int u, v, w, x;while (m--){scanf("%d%d%d", &u, &v, &w);G[u][v] = w; G[v][u] = w;}
}int mintree() //默认从第一个城镇开始,函数返回最小生成树边权之和
{d[1] = 0;  //第一个城镇到自身的最小花费为0;ans = 0;for (int i = 1; i <= n; i++){int u = -1, min = inf;for (int j = 1; j <= n; j++){if (visit[j] == false && d[j] < min){u = j;min = d[j];} //用来判断未访问点中 d[]最小的;}if (u == -1)return -1;  //如果u值为-1,则表示两地点间不连通;visit[u] = true;ans += d[u];  //进行最小边权值相加for (int v = 1; v <= n; v++){if (visit[v] == false && G[u][v] != inf && G[u][v] < d[v]){d[v] = G[u][v];}  //比较目前城市到目标城市的距离和起始点到目标城市的距离}}return ans;
}void answer(int ans)
{delete[]visit;delete[]d;if (ans == -1)printf("Impossible\n");elseprintf("%d\n", ans);
}int main()
{cin >> n >> m;Init();answer(mintree());return 0;
}

最小生成树优化(Kruskal并查集实现) 

挖沟 (nowcoder.com)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
class Node
{
public:int A, B, len;Node(int a, int b, int c){A = a;B = b;len = c;}
};
int fa[maxn], N, M, K, A, B, C, ans;
vector<Node>v;
int find(int x)
{return x == fa[x] ? x : fa[x] = find(fa[x]);
}
bool cmd(Node& A, Node& B)
{return A.len < B.len;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> N >> M;for (int i = 1; i <= N; i++)fa[i] = i;for(int i = 0; i < M; i++){cin >> A >> B >> C;v.emplace_back(A, B, C);}sort(v.begin(), v.end(),cmd);int sum = N;for (int i = 0; i < M; i++){int x = find(fa[v[i].A]);int y = find(fa[v[i].B]);if (x == y)continue;//自己指向自己不用计算并且已经入图的点也无需计算fa[x] = y;ans += v[i].len;sum--;if(1 == sum)break;}return cout << ans, 0;
}

道路建设 (nowcoder.com)Kruskal算法实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 110;
int N, M , K, sum, fa[maxn],A,B,len,ans;    
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
struct Node
{int A , B ,len;Node(int a,int b,int c){A = a,B = b,len = c;}
};
bool cmd(Node A,Node B)
{return A.len < B.len;
}
vector<Node>v;
signed main()
{cin >> sum >> N >> M;for(int i = 1;i <= M;i++)fa[i] = i;for(int i = 1;i <= N;i++){cin >> A >> B >> len;v.emplace_back(A,B,len);}sort(v.begin(),v.end(),cmd);int K = N;for(int i = 0;i < N;i++){int x = find(fa[v[i].A]);int y = find(fa[v[i].B]);if(x == y)continue;fa[x] = y;ans += v[i].len;K--;if(K == 1)break;}ans <= sum ? cout << "Yes" : cout << "No" ;return 0;
}

Forsaken喜欢独一无二的树 (nowcoder.com)

重构最小生成树(Kruskal)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 10;
int N, M, K, sum, fa[maxn], A, B, len, ans;
struct Node {int A, B, len; Node(int a, int b, int c) { A = a, B = b; len = c; }
};int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }bool cmd(Node A, Node B) { return A.len < B.len; }vector<Node>v;void Kruskal(){sort(v.begin(), v.end(), cmd);for (int i = 0; i < M; ){//对于M条选择进行枚举int j;for (j = i; v[i].len == v[j].len; j++){//最小生成树每一步都取最优解,如果出现多种最小生成树的情况,那么一定是有N条边权是相同的,将其全部记录下来if (find(v[j].A) != find(v[j].B))//前提条件:A B点为被纳入最小生成树中ans += v[j].len;}for (; i < j; i++){int fx = find(v[i].A), fy = find(v[i].B);if (fx != fy) fa[fx] = fy, ans -= v[i].len;//保留一条最优的生成树路径}}cout << ans;}signed main(){cin >> N >> M;for (int i = 1; i <= N; i++)fa[i] = i;for (int i = 1; i <= M; i++){cin >> A >> B >> len;v.emplace_back(A, B, len);}Kruskal();return 0;}

[SCOI2012]滑雪与时间胶囊 (nowcoder.com)

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int N = 1e6 + 5;
const double eps = 1e-10;
const int mod = 1e9 + 7;
typedef long long ll;
struct Edge {int v, nextz;ll cost;
}edge[N << 1];
int tot, head[N];
void addedge(int u, int v, ll w) {edge[tot].v = v;edge[tot].cost = w;edge[tot].nextz = head[u];head[u] = tot++;
}
struct qnode {int v, h;ll dis;qnode(int _v = 0,int  _h = 0, ll _dis = 0): v(_v), h(_h), dis(_dis){}bool operator < (const qnode &s) const {return h == s.h ? dis > s.dis : h < s.h;}
};int val[N], cnt, n, m;;
bool vis[N];
ll dist[N], ans;
void prim() {for(int i = 1; i <= n; i++) dist[i] = inf;priority_queue<qnode> q;q.push(qnode(1, val[1], 0));dist[1] = 0;while(!q.empty()) {qnode tmp = q.top();q.pop();int u = tmp.v;if(vis[u]) continue;vis[u] = 1;cnt++, ans += dist[u];for(int i = head[u]; ~i; i = edge[i].nextz) {int v = edge[i].v;ll cost = edge[i].cost;if(!vis[v] && dist[v] > cost) {dist[v] = cost;q.push(qnode(v, val[v], dist[v]));}}}
}
int main() {cin.tie(0)->sync_with_stdio(false);memset(head, -1, sizeof(head));cin >> n >> m;            for(int i = 1; i <= n; i++) cin >> val[i];while(m--) {int u, v;ll w;cin >> u >> v >> w;if(val[u] >= val[v]) addedge(u, v, w);if(val[v] >= val[u]) addedge(v, u, w);}prim();cout << cnt << ' ' << ans << "\n";return 0;
}


http://www.ppmy.cn/news/83062.html

相关文章

Windows中的Tomcat服务器安装证书并设置强制https访问

官网参考 阿里云 华为云 获取证书 自己生成证书 这边介绍一个生产开发环境证书的方式&#xff1a;使用 Java 提供的工具&#xff1a;keytool keytool -genkeypair -alias "tomcat" -keyalg "RSA" -keystore "d:\tomcat.keystore" Tomcat服…

Springboot +spring security,登录用户数据获取

一.简介 前面章节学习了登录表单的配置并且对源码进行了简单的分析&#xff0c;现在有个问题了&#xff0c;既然用户登录了&#xff0c;那么如何在接口中获取用户信息呢。这篇文章就来看下这个问题&#xff0c;代码中获取登录用户信息。 二.创建项目 如何创建一个SpringSecu…

设计模式 (一) 入门

目录 设计模式系列文章主要包含 1.什么是设计模式&#xff1f; 2.设计模式的分类 2.1 创建型设计模式 2.2 结构型设计模式 2.3 行为型设计模式 设计模式系列文章主要包含 设计模式 (一) 入门 设计模式 (二) 创建型设计模式系列 设计模式 (三) 结构型设计模式系列 …

平台使用篇 | 批处理(bat)脚本使用教程(三)

导读 本讲针对RflySim平台的一些特点简要介绍了平台使用批处理技术的原因&#xff0c;并根据CopterSim中仿真功能区的参数设置阐述了批处理技术在平台中的具体运用。 平台使用篇 | 批处理(bat)脚本使用教程(三&#xff09; RflySim平台使用批处理技术的原因 ①调用多个软件Rf…

【DNDC模型】农田生态、陆地生态系统的动态模拟模型

DNDC模型 DNDC模型是一个用于模拟和追踪农业生态系统中碳氮生物地球化学循环的过程模型&#xff0c;可以用来模拟农业生态系统碳氮排放、农作物产量、土壤固碳作用以及硝酸盐淋失等过程。 模型由两部分组成&#xff1a;第一部分包括土壤气候、植物生长和有机质分解等3个子模型…

热门 API 大全分享(含天气、物流等)

最近收录了一些常用、免费的 API 接口&#xff0c;在这里记录分享给大家~ 天气预报查询&#xff1a;查询全国以及全球多个城市的天气&#xff0c;包含15天天气预报查询。空气质量查询&#xff1a; 查询国内3400个城市的整点观测&#xff0c;获取指定城市的整点观测空气质量。分…

【2023 雷泽杯 · Misc】我是签到题

一道图片隐写题 目录 一、题目 二、思路 1.010editor查看源码 2.检索头部关键字段 3.图片隐写——高度隐写 一、题目 看不到这个图片对吧&#xff0c;这就是题目原本的样子。 二、思路 1.010editor查看源码 很明显的rar特征&#xff0c;尝试将后缀改成rar后打开。 发…

Redis 高可用之持久化

1.Redis 高可用的相关知识 1.1 什么是高可用 在web服务器中&#xff0c;高可用是指服务器可以正常访问的时间&#xff0c;衡量的标准是在多长时间内可以提供正常服务(99.9%、99.99%、99.999%等等)。 但是在Redis语境中&#xff0c;高可用的含义似乎要宽泛一些&#xff0c;除了…