【HDU 1863 畅通工程】
发布日期:2021-11-04 12:58:48
浏览次数:6
分类:技术文章
本文共 1596 字,大约阅读时间需要 5 分钟。
畅通工程
Problem Description
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。经过调查评估,得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序,计算出全省畅通需要的最低成本。Input
测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 );随后的 N 行对应村庄间道路的成本,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间道路的成本(也是正整数)。为简单起见,村庄从1到M编号。当N为0时,全部输入结束,相应的结果不要输出。Output
对每个测试用例,在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通,则输出“?”。Sample Input
3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100Sample Output
3 ?prime算法 :
#include#include #define INF 0x3f3f3f int lowcost[110],visit[110],map[110][110]; int city; void prime() { int i,j; int next,min,mincost=0; memset(visit,0,sizeof(visit)); for(i=1;i<=city;i++) { lowcost[i]=map[1][i]; } visit[1]=1; for(i=1;i lowcost[j]) //找到一条可以修的最短路 { min=lowcost[j]; next=j; } } if(min==INF)//遍历全部找不到与该点连通的线路 { printf("?\n"); return ;//程序结束 } mincost+=min; visit[next]=1; for(j=1;j<=city;j++) { if(!visit[j]&&lowcost[j]>map[next][j]) //更新能连接该点的最短路 { lowcost[j]=map[next][j]; } } } printf("%d\n",mincost); } int main() { int road,need; int i,j,x,y,c; while(scanf("%d%d",&road,&city)&&(road!=0)) { memset(map,INF,sizeof(map)); while(road--) { scanf("%d%d%d",&x,&y,&c); map[x][y]=map[y][x]=c; } prime(); } return 0; }
转载地址:https://blog.csdn.net/WYK1823376647/article/details/52254313 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月29日 13时08分13秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
android 一个动态添加控件和删除控件的例子
2019-05-08
bash学习笔记2 使用结构化命令
2019-05-08
ListView
2019-05-08
Android入门笔记: 08 单选框与复选框
2019-05-08
Android入门笔记: ListView和一个控制类
2019-05-08
Bash学习笔记03 : 更多结构化命令 for和 while
2019-05-08
Android入门笔记10: AutoCompleteTextView 自动补全文本
2019-05-08
Timer的用法和PorgressBar
2019-05-08
SeekBar
2019-05-08
Android入门笔记12: GridView ProgressDialog
2019-05-08
Android入门笔记13: Notification
2019-05-08
Android入门笔记14: ScrollView RatingBar
2019-05-08
Android入门笔记15: ImgeSwitcher Gallery
2019-05-08
Android入门笔记16: EditText 和 返回键
2019-05-08
最快速的Android开发环境搭建ADT-Bundle及Hello World
2019-05-08
head tail icovn
2019-05-08
eclipse不自动生成MainActivity
2019-05-08
Android入门笔记17 颜色资源 尺寸资源
2019-05-08
Android入门笔记18 字符串资源 国际化 数组资源
2019-05-08