2760: DS2025-综合应用题
金币值：0
定数：1
时间限制：1.000 s
内存限制：128 M
解决：11
提交：20
正确率：55.00% 命题人：
题目描述
城市旅游景点柏油公路建设:随着中国改革开放的不断深入，人们的生活水平越来越高，越来越多的人希望利用假期前往国内各旅游景点游览，在放松心情的同时领略祖国的大好河山，激发民族自豪感。假设国内有 $n$ 个主要旅游景点，管理部门希望任意两个景点之间都能通过柏油公路连通（即形成一个连通网络）。由于建设资金有限，管理部门希望以最小的总成本完成柏油公路网络建设。已知任意两个景点之间均可修建柏油公路，且每条公路的建设成本已知。现在需要设计一个算法，输出连通所有景点的最小成本。
测试代码 复制
#include<stdio.h>
#define MAXSIZE 100 // 最大顶点数由用户定义
#define INFINITY 65535
typedef struct {
int a[MAXSIZE][MAXSIZE]; //邻接矩阵，下标从0开始使用
int n; //图中顶点数
int m; //图中边数
}Graph;
void CreateGraph(Graph &g); //建立图的邻接矩阵
int minSpanTree(Graph G,int v); //返回最小生成树上所有边上权重之和
int main(void) {
Graph g;
scanf("%d %d",&g.n,&g.m);
CreateGraph(g);
int min=minSpanTree(g,0);
printf("%d\n",min); //输出最小代价
return 0;
}
void CreateGraph(Graph &g){ //建立图的邻接矩阵
________
}
int minSpanTree(Graph g, int v) { //求从顶点v出发求最小生成树代价
________
}输入
第一行输入一个整数，表示图中的顶点数；
第二行输入一个整数，表示图中的边数；
接下来输入 $m$ 行，每行有 $3$ 个整数，分别表示图中边的两个顶点编号以及该边的权。
第二行输入一个整数，表示图中的边数；
接下来输入 $m$ 行，每行有 $3$ 个整数，分别表示图中边的两个顶点编号以及该边的权。
输出
输出满足要求的最小成本。
样例输入 复制
3
3
0 1 10
1 2 20
2 0 30样例输出 复制
30