优客文库提供全面的范文格式和文档模板,包括申请书、合同、借据、证明、求职信等,助力您快速撰写专业文档。

用C语言完成:用连通网中的顶点表示城市,边上的权值表示在这两个城市建立通信所花费的代价。求要连通所有的城市所花费的最小代价,要求构造最小生成树,并完成输入输出的案例

来自 河南省安阳市 的网友 时间: 热度:20°C 加入收藏 我要投稿 点赞(4)
解析:这是一个典型的最小生成树问题,可以使用Kruskal算法或Prim算法来解决。这里我们使用Kruskal算法来实现。首先需要定义一个边的结构体,包含两个顶点和权值。然后创建一个并查集来维护连通性。接着从最小的边开始遍历,如果加入这条边不会破坏连通性,就将其加入最小生成树。最后输出最小生成树的总权值。

代码如下:

```c
#include <stdio.h>
#include <stdlib.h>

typedef struct Edge {
int u, v, w;
} Edge;

int cmp(const void *a, const void *b) {
return ((Edge *)a)->w - ((Edge *)b)->w;
}

int find(int x, int *parent) {
if (parent[x] == x) {
return x;
}
return parent[x] = find(parent[x], parent);
}

void union_set(int x, int y, int *parent) {
int root_x = find(x, parent);
int root_y = find(y, parent);
if (root_x != root_y) {
parent[root_y] = root_x;
}
}

int main() {
int n, m;
scanf("%d %d", &n, &m);
Edge edges[m];
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
}
qsort(edges, m, sizeof(Edge), cmp);

int parent[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
}

int ans = 0;
for (int i = 0; i < m; i++) {
int u = edges[i].u;
int v = edges[i].v;
int w = edges[i].w;
if (find(u, parent) != find(v, parent)) {
ans += w;
union_set(u, v, parent);
}
}

printf("%d
", ans);
return 0;
}
```

输入输出案例:

```
输入:
5 7
1 2 3
1 3 4
2 4 5
2 5 6
3 5 7
输出:
11
```
221381
领取福利

微信扫码领取福利

微信扫码分享

直接下载
单次下载
0.5元/次
支付宝支付
2.免费下载(每天5次)
公众号:试题试卷下载复制
复制微信公众,搜索即可关注!
扫一扫关注公众号
欢迎使用微信支付
扫一扫支付
金额:
常见问题

请登录之后再下载!

下载中心

您的账号注册成功!密码为:123456,当前为默认信息,请及时修改

下载文件立即修改

帮助中心

如何获取自己的订单号?

打开微信,找到微信支付,找到自己的订单,就能看到自己的交易订单号了。

阅读并接受《用户协议》
注:各登录账户无关联!请仅用一种方式登录。


用户注册协议

一、 本网站运用开源的网站程序平台,通过国际互联网络等手段为会员或游客提供程序代码或者文章信息等服务。本网站有权在必要时修改服务条款,服务条款一旦发生变动,将会在重要页面上提示修改内容或通过其他形式告知会员。如果会员不同意所改动的内容,可以主动取消获得的网络服务。如果会员继续享用网络服务,则视为接受服务条款的变动。网站保留随时修改或中断服务而不需知照会员的权利。本站行使修改或中断服务的权利,不需对会员或第三方负责。

关闭