PTA7-1 公路村村通 分数 20 作者 陈越 单位 浙江大学

这篇具有很好参考价值的文章主要介绍了PTA7-1 公路村村通 分数 20 作者 陈越 单位 浙江大学。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。

输入格式:
输入数据包括城镇数目正整数N(≤1000)和候选道路数目M(≤3N);随后的M行对应M条道路,每行给出3个正整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从1到N编号。

输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通,则输出−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
输出样例:
12
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB

答案:文章来源地址https://www.toymoban.com/news/detail-755116.html

# include <stdio.h>
# include <stdlib.h>
# define MAXV 1010
# define INF 9999

typedef struct GNode
{
	int V[MAXV];
	int E[MAXV][MAXV];
	int n, e;
}GNode;

GNode* CreateGraph()
{
	GNode* G;
	G = (GNode*)malloc(sizeof(GNode));
	int num1, num2, cost;//输入数据

	scanf("%d %d", &(G->n), &(G->e));
	for (int i = 1; i <= G->n; i++)G->V[i] = i;//顶点集初始化
	for (int i = 1; i <= G->n; i++)//边集初始化
	{
		for (int j = 1; j <= G->n; j++)G->E[i][j] = INF;
	}

	for (int i = 1; i <= G->e; i++)
	{
		scanf("%d %d %d", &num1, &num2, &cost);
		G->E[num1][num2] = cost;
		G->E[num2][num1] = cost;//因为此图为无向图,所以邻接矩阵对称
	}
	return G;
}

void Prim(GNode* G)
{
	int lowcost[MAXV];
	int count = 1;//n个顶点无向图的最小生成树有n-1条边。
	int min, minId, sum = 0;

	for (int i = 1; i <= G->n; i++)lowcost[i] = G->E[1][i];

	lowcost[1] = 0;

	while (count < G->n)
	{
		min = INF;
		for (int i = 1; i <= G->n; i++)
		{
			if (lowcost[i] != 0 && lowcost[i] < min)
			{
				min = lowcost[i];
				minId = i;
			}
		}
		count++;
		lowcost[minId] = 0;
		sum += min;

		for (int i = 1; i <= G->n; i++)
		{
			if (lowcost[i] != 0 && G->E[minId][i] < lowcost[i])lowcost[i] = G->E[minId][i];
		}
	}

	if (sum > INF)printf("-1");
	else printf("%d", sum);
}

int main()
{
	GNode* G;
	G = CreateGraph();
	Prim(G);
	return 0;
}

到了这里,关于PTA7-1 公路村村通 分数 20 作者 陈越 单位 浙江大学的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • pta7-5 利用二分查找搜寻所有待查找数据

    利用二分法在一个有N(N≤20)个元素的有序数列中查找指定值y。找到y后,先输出查找次数,再输出其在数组中对应的下标。若数列中存在多个y,将所有y的位置按下标序号顺序输出; 否则输出“not found”. 输入格式: 输入在第1行中给出1个不大于20的数N。在第2行给出N个数(

    2024年02月04日
    浏览(31)
  • PTA 编程题(C语言)-- 高速公路超速处罚

     题目作者:陈建海  浙江大学 按照规定,在高速公路上行使的机动车,达到或超出本车道限速的10%则处200元罚款;若达到或超出50%,就要吊销驾驶证。请编写程序根据车速和限速自动判别对该机动车的处理。 输入格式: 输入在一行中给出2个正整数,分别对应车速和限速,其

    2024年02月08日
    浏览(41)
  • PTA 2 时钟类-1(用默认的构造方法)分数 10

    先看题: 定义一个时钟类MyClock,包含3个数据成员(即成员变量:时,分,秒);包含2个方法, 一个设置时间的方法setClock(),一个显示时间的方法display(),按照“ 12:28:45 ”的格式显示时间。 请在下面的【】处补充代码: 输入格式: 输入一个时间:(时 分 秒用空格分隔)。

    2024年02月06日
    浏览(28)
  • 【PTA题目】7-11 求矩阵的局部极大值 分数 15

    7-11 求矩阵的局部极大值 分数 15 全屏浏览题目 切换布局 作者 徐镜春 单位 浙江大学 给定M行N列的整数矩阵A,如果A的非边界元素A[i][j]大于相邻的上下左右4个元素,那么就称元素A[i][j]是矩阵的局部极大值。本题要求给定矩阵的全部局部极大值及其所在的位置。 输入格式:

    2024年02月04日
    浏览(43)
  • 【PTA] 作者 李祥单位 湖北经济学院6-1到6-12 顺序表

    6-1 顺序表 - 3. 创建线性表 6-2 顺序表 - 4. 销毁线性表 6-3 顺序表 - 12. 线性表长度 6-4 顺序表 - 6. 插入元素 6-5 顺序表 - 8. 删除元素 6-6 顺序表 - 9. 清空线性表 6-7 顺序表 - 7. 输出线性表 6-8 顺序表 - 10. 输入线性表 6-9 顺序表 - 14. 读取元素 6-10 顺序表 - 19. 查找元素 6-11 顺序表 -

    2024年02月07日
    浏览(32)
  • PTA L1-095 分寝室 (20 分)

    学校新建了宿舍楼,共有 n n n 间寝室。等待分配的学生中,有女生 n 0 n_0 n 0 ​ ​ 位、男生 n 1 n_1 n 1 ​ ​位。所有待分配的学生都必须分到一间寝室。所有的寝室都要分出去,最后不能有寝室留空。 现请你写程序完成寝室的自动分配。分配规则如下: 男女生不能混住; 不

    2023年04月23日
    浏览(37)
  • 高速公路巡检无人机,为何成为公路巡检的主流工具

    随着无人机技术的不断发展,无人机越来越多地应用于各个领域。其中,在高速公路领域,高速公路巡检无人机已成为公路巡检的得力助手。高速公路巡检无人机之所以能够成为公路巡检中的主流工具,主要是因为其具备以下三大特性。 一、高速公路巡检无人机的高效性 高

    2024年02月14日
    浏览(89)
  • 交通气象站——多要素观测、智慧公路

    车辆在高速公路中的车速较快,在天气恶劣的情况下,极易引发交通事故,其中,对高速公路交通影响较大的因素主要有有暴雨、雾、雾、雪、沙尘暴、道路结冰、极端气温和大风等。为了确保高速公路交通的安全运行,有必要对这些天气现象进行观测。交通气象站是对温度

    2024年02月10日
    浏览(41)
  • 数字基建-高速公路智慧建造管控平台

    孝汉应高速公路(福银高速至武荆高速段)路线起点位于孝南区肖港以西的杨家桥,设孝感北枢纽互通接福银高速公路,终点位于汉川市麻河镇东北的肖杨角到达,并设麻河枢纽互通与武荆高速公路对接,主线全长 34.484 公里。 本工程共设置桥梁 20555m/17座,互通式立交5处,

    2024年02月16日
    浏览(36)
  • 高速公路和 TCP/IP 的负载均衡和拥塞

    长假小长假返程堵车问题非常有趣,很多人都在抱怨,新闻也在各种报道,但这么多年几乎没人想办法绕开拥堵,明知道那个时间那条路会堵,却依然在那个时间涌入那条路。 ​这件事其实很容易解释,人们内心对这种拥堵是容忍的,是可预期的,也就是说人们在假期里专门

    2024年02月07日
    浏览(30)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包