HDOJ 1233 还是畅通工程

2023-12-13 20:38
文章标签 工程 畅通 hdoj 1233

本文主要是介绍HDOJ 1233 还是畅通工程,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

还是畅通工程

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 35940    Accepted Submission(s): 16212


Problem Description
某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。

Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。
当N为0时,输入结束,该用例不被处理。

Output
对每个测试用例,在1行里输出最小的公路总长度。

Sample Input
  
3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0

Sample Output
  
3 5
Hint
Hint
Huge input, scanf is recommended.

Source
浙大计算机研究生复试上机考试-2006年  


/*
网址 http://acm.hdu.edu.cn/showproblem.php?pid=1233 
*/#include<stdio.h> 
#include<string.h>const int N=110;
int map[N][N];       //创建地图,邻接矩阵 
int mark[N];         //用于标记map[][]是否被访问 
int i,j,n;int prim(){int sum=0;int min,t,k;t=n;while(--t){min=100000; //int 型所不能达到的数,意味着两点无限远 for(i=2;i<=n;i++){if(mark[i]!=1&&min>map[1][i]){min=map[1][i];k=i;}}sum=sum+min;mark[k]=1;for(i=2;i<=n;i++){if(mark[i]!=1&&map[k][i]<map[1][i]){map[1][i]=map[k][i];}}}return sum;
}int main(){int x,y,num,l;while(scanf("%d",&n)&&n){num=n*(n-1)/2;memset(map,0,sizeof(map));for(i=1;i<=num;i++){scanf("%d%d%d",&x,&y,&l);map[x][y]=map[y][x]=l;}memset(mark,0,sizeof(mark));printf("%d\n",prim());}return 0;
}


这篇关于HDOJ 1233 还是畅通工程的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/489890

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

Jenkins构建Maven聚合工程,指定构建子模块

一、设置单独编译构建子模块 配置: 1、Root POM指向父pom.xml 2、Goals and options指定构建模块的参数: mvn -pl project1/project1-son -am clean package 单独构建project1-son项目以及它所依赖的其它项目。 说明: mvn clean package -pl 父级模块名/子模块名 -am参数

二、Maven工程的创建--JavaSEJavaEE

1、idea创建Maven JavaSE工程:  2、idea创建Maven JavaEE工程:   (1)手动创建 (2)插件方式创建 在idea里安装插件JBLJavaToWeb; 选择需要生成的项目文件后,右击: 项目的webapp文件夹出现小蓝点,代表成功。

三、Maven工程的构建

首先,创建和构建是两个概念。 构建是指将源代码、依赖库和资源文件等转换为可执行或可部署的应用程序的过程。 在这个过程中包括编译源代码、链接依赖库、打包和部署等多个步骤。 项目构建是软件开发过程中至关重要的一部分,它能够大大提高软件开发效率,使得开发人员更加专注于应用程序的开发和维护,而不必关心应用程序的构建细节。 同时,项目构建还能将多人写的代码聚合,并能够自动化项目的构建和部署,

我在高职教STM32——准备HAL库工程模板(1)

新学期开学在即,又要给学生上 STM32 嵌入式课程了。这课上了多年了,一直用的都是标准库来开发,已经驾轻就熟了。人就是这样,有了自己熟悉的舒适圈,就很难做出改变,老师上课也是如此,排斥新课和不熟悉的内容。显然,STM32 的开发,HAL 库已是主流,自己其实也在使用,只不过更换库就意味着教学内容有很大变化,自己也就迟迟没有迈出调整这一步。现在,是时候做出变化了,笔者计划保持教学项

java工程的导入jar包

由于现在学习java web,java工程导入jar包都忘记了。 在此想记录一下:工程项目名:右击 -- Build Path --add External Archives 点击会弹出一个框 ,选择你要导入的jar路径就可以了。

【MyBatis学习14】MyBatis的逆向工程生成代码

1. 什么是逆向工程 mybatis的一个主要的特点就是需要程序员自己编写sql,那么如果表太多的话,难免会很麻烦,所以mybatis官方提供了一个逆向工程,可以针对单表自动生成mybatis执行所需要的代码(包括mapper.xml、mapper.java、po..)。一般在开发中,常用的逆向工程方式是通过数据库的表生成代码。 2. 使用逆向工程 使用mybatis的逆向工程,需要导入逆向

maven-聚合工程

聚合工程: 聚合工程里可以分为顶级项目(顶级工程、父工程)与子工程,这两者的关系其实就是父子继承的关系,子工程在maven里称之为模块(module),模块之间是平级,是可以相互依赖的。子模块可以使用顶级工程里所有的资源(依赖),子模块之间如果要使用资源,必须构建依赖(构建关系)一个顶级工程是可以由多个不同的子工程共同组合而成。

图特征工程实践指南:从节点中心性到全局拓扑的多尺度特征提取

图结构在多个领域中扮演着重要角色,它能有效地模拟实体间的连接关系,通过从图中提取有意义的特征,可以获得宝贵的信息提升机器学习算法的性能。 本文将介绍如何利用NetworkX在不同层面(节点、边和整体图)提取重要的图特征。 本文将以NetworkX库中提供的Zachary网络作为示例。这个广为人知的数据集代表了一个大学空手道俱乐部的社交网络,是理解图特征提取的理想起点。 我们先定义一些辅助函数