热门标签 | HotTags
当前位置:  开发笔记 > 程序员 > 正文

NYOJ38布线问题(Prim)

布线问题时间限制:1000ms|内存限制:65535KB难度:4描述南阳理工学院要进行用电线路改造,现在校长要求设计师设计出一种布线方式,该布线方式需要满足以下条件:1、把所有的楼都供上电

布线问题

时间限制:1000 ms  |  内存限制:65535 KB难度:4
描述
南阳理工学院要进行用电线路改造,现在校长要求设计师设计出一种布线方式,该布线方式需要满足以下条件:
1、把所有的楼都供上电。
2、所用电线花费最少
输入
第一行是一个整数n表示有n组测试数据。(n<5)
每组测试数据的第一行是两个整数v,e.
v表示学校里楼的总个数(v<=500)
随后的e行里,每行有三个整数a,b,c表示a与b之间如果建铺设线路花费为c(c<=100)。(哪两栋楼间如果没有指明花费,则表示这两栋楼直接连通需要费用太大或者不可能连通)
随后的1行里,有v个整数,其中第i个数表示从第i号楼接线到外界供电设施所需要的费用。( 0(楼的编号从1开始),由于安全问题,只能选择一个楼连接到外界供电设备。
数据保证至少存在一种方案满足要求。
输出
每组测试数据输出一个正整数,表示铺设满足校长要求的线路的最小花费。
样例输入
1
4 6
1 2 10
2 3 10
3 1 10
1 4 1
2 4 1
3 4 1
1 3 5 6
样例输出
4
/*
Time:2014-8-30 21:51
*/
#include
#include
#include
using namespace std;
const int INF=1<<20;
int minV=INF;
int N,M;
int map[505][510];
void Init(){
scanf("%d%d",&N,&M);
for(int i=0;i<=N;i++)
for(int j=0;j<=N;j++){
if(j!=i)map[i][j]=INF;
else map[j][i]=0;
}
for(int i=0;iint a,b,c;
scanf("%d%d%d",&a,&b,&c);
map[a][b]=map[b][a]=c;
}
minV=INF;int cost;
for(int i=0;iscanf("%d",&cost);
minV=min(minV,cost);
}
}
int Prim(){
int d[1000];
int Mst=0;
bool vis[1000];
memset(vis,0,sizeof(vis));
for(int i=1;i<=N;i++)
d[i]=map[1][i];
vis[1]=true;
for(int i=1;iint u=0,m=INF;
for(int j=1;j<=N;j++){
if(!vis[j]&&m>d[j]){
m=d[j];
u=j;
}
}
vis[u]=true;
if(d[u]==INF)return Mst;
Mst+=d[u];
for(int j=1;j<=N;j++){
if(!vis[j]&&d[j]>map[u][j]){
d[j]=map[u][j];
}
}
}
return Mst;
}
void solve(){
int T;
scanf("%d",&T);
while(T--){
Init();
int Mst=Prim();
printf("%d\n",Mst+minV);
}
}
int main(){
solve();
return 0;
}


推荐阅读
  • 兆芯X86 CPU架构的演进与现状(国产CPU系列)
    本文详细介绍了兆芯X86 CPU架构的发展历程,从公司成立背景到关键技术授权,再到具体芯片架构的演进,全面解析了兆芯在国产CPU领域的贡献与挑战。 ... [详细]
  • 2020年9月15日,Oracle正式发布了最新的JDK 15版本。本次更新带来了许多新特性,包括隐藏类、EdDSA签名算法、模式匹配、记录类、封闭类和文本块等。 ... [详细]
  • 随着互联网的普及,网站的安全性成为用户关注的重点。本文将探讨芒果XO(www.mangoxo.com)是否存在病毒风险,并介绍常见的五种病毒类型。 ... [详细]
  • 过去查询Mysql的时候,都见3306对所有端口开放着,感觉不安全。netstat&nbsp;-anlp&nbsp;|&nbsp;grep&nbsp;mysqltcp&nbsp;0&am ... [详细]
  • 越来越多的家庭在装修淋浴房时选择不铺设传统瓷砖,而是采用四边走水的设计,这种设计不仅排水迅速,还能提升整体美感。本文将详细介绍这一趋势及其优点。 ... [详细]
  • 近期,微信公众平台上的HTML5游戏引起了广泛讨论,预示着HTML5游戏将迎来新的发展机遇。磊友科技的赵霏,作为一名HTML5技术的倡导者,分享了他在微信平台上开发HTML5游戏的经验和见解。 ... [详细]
  • 本文详细介绍了MySQL数据库服务器(mysqld)和客户端(mysql)的区别,并提供了多种启动和关闭MySQL服务器的方法。通过这些方法,您可以更好地管理和维护MySQL数据库。 ... [详细]
  • 本文介绍如何使用OpenCV和线性支持向量机(SVM)模型来开发一个简单的人脸识别系统,特别关注在只有一个用户数据集时的处理方法。 ... [详细]
  • 用阿里云的免费 SSL 证书让网站从 HTTP 换成 HTTPS
    HTTP协议是不加密传输数据的,也就是用户跟你的网站之间传递数据有可能在途中被截获,破解传递的真实内容,所以使用不加密的HTTP的网站是不 ... [详细]
  • 如何在服务器上配置SSL证书
    SSL证书是用于验证互联网上身份的一种数字凭证,通过启用HTTPS协议,确保用户与服务器之间的通信安全。本文将详细介绍如何在API和服务器上配置SSL证书,以提升网站的安全性和可信度。 ... [详细]
  • 解决启动时遇到 'NTLDR is Missing' 错误
    本文详细介绍了如何解决 Windows XP 系统启动时出现的 'NTLDR is Missing' 错误,提供了多种修复方法。 ... [详细]
  • IOS Run loop详解
    为什么80%的码农都做不了架构师?转自http:blog.csdn.netztp800201articledetails9240913感谢作者分享Objecti ... [详细]
  • Ping 命令的高级用法与技巧
    本文详细介绍了 Ping 命令的各种高级用法和技巧,帮助读者更好地理解和利用这一强大的网络诊断工具。 ... [详细]
  • 国联物流是一家由国家出资设立的国有企业,全称为湖南国联物流有限公司,成立于2001年3月,前身为株洲国联货运部。公司现办公地点位于湖南长沙,专注于大件运输、药品配送及第三方物流服务。 ... [详细]
  • 本文详细介绍了如何使用OpenSSL自建CA证书的步骤,包括准备工作、生成CA证书、生成服务器待签证书以及证书签名等过程。 ... [详细]
author-avatar
mobiledu2502887593
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有