畅通project(杭电1863)
project 杭电 畅通
2023-09-14 09:10:09 时间
畅通project
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 17882 Accepted Submission(s): 7561
Problem Description
省政府“畅通project”的目标是使全省不论什么两个村庄间都能够实现公路交通(但不一定有直接的公路相连,仅仅要能间接通过公路可达就可以)。经过调查评估,得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编敲代码,计算出全省畅通须要的最低成本。
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 100
Sample Output
3 ?#include<stdio.h> #include<algorithm> using namespace std; int pre[105]; struct st { int a,b; int p; }data[105]; int find(int n) //找结点的根; { return pre[n]==n?n:pre[n]=find(pre[n]); } int join(int x,int y) // { int fx=find(x),fy=find(y); if(fx!=fy) //假设两结点的根并不是为同一个点。连接起来。 { pre[fx]=fy; return 1; } return 0; } int cmp(st a,st b) //将修路的价钱按升序排列。 { return a.p<b.p; } int main() { int i,m,n; while(~scanf("%d %d",&m,&n),m) { for(i=1;i<=n;i++) //将结点独立(初始化); { pre[i]=i; } for(i=1;i<=m;i++) { scanf("%d %d %d",&data[i].a,&data[i].b,&data[i].p); } sort(data+1,data+m+1,cmp); //从i=1排序,n个数据,所以是sort(data+1,data+m+1,cmp); int sum=0,ans=0; for(i=1;i<=m;i++) { if(join(data[i].a,data[i].b)) //假设两节点的根为同一个根,则不须要修路,反之选修路花费较少的一条路(排序的作用)。 { sum+=data[i].p; } } for(i=1;i<=n;i++) //统计剩下孤立点的个数。间接统计须要修多少路。 { if(pre[i]==i) { ans++; } } if(ans>1) printf("?\n"); else printf("%d\n",sum); } return 0; }
相关文章
- This version of Android Studio cannot open this project, please retry with Android Studio 4.0 or newer.
- [Cloud DA] Serverless Framework with AWS - Part 0: Serverless Project structure
- [Kotlin Spring boot] Enable automatically recompile for Spring boot project with devtool
- GNU M4 - GNU Project - 免费软件基金会(FSF)
- Annotation request in WebIDE automatic generated project
- how to resolve 404 not found error for sap-ui-core.js after project is cloned to
- 搭建Dynamic Web Project(动态web项目)的springmvc工程1
- 【Android Gradle 插件】Android 依赖管理 ③ ( dependencies 依赖配置 | Project#dependencies 函数分析 | 自定义依赖配置 )
- 【Android Gradle 插件】Gradle 构建生命周期 ① ( 分析构建脚本 | 执行初始化配置 | 执行 Gradle 任务 | Project#beforeEvaluate 函数 )
- vs2015中无法设置Qt版本,qt project setting 是灰色,Qt无法编译ui文件
- 【大数据project师之路】Hadoop——MapReduce概述
- 每一个人都懂得敏捷开发 (软件project), 为何产品开发的效率与质量还是这么的烂?
- 【三】3D匹配Matching之外形匹配Shape—Based——project_shape_model_3d()/read_shape_model_3d()算子
- Harbor 调用API批量创建project
- 首次将IDEA中的项目上传到Github / Share Project on GitHub