hdu_1863_畅通工程_201403122000
2024-10-21 03:41:41
畅通工程
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14215 Accepted Submission(s): 5875
Problem Description
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。经过调查评估,得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序,计算出全省畅通需要的最低成本。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 );随后的 N
行对应村庄间道路的成本,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间道路的成本(也是正整数)。为简单起见,村庄从1到M编号。当N为0时,全部输入结束,相应的结果不要输出。
行对应村庄间道路的成本,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间道路的成本(也是正整数)。为简单起见,村庄从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 ?
Source
#include <cstdio>
#include <iostream>
#include <cstring>
//#include <algotithm>
#include <stdlib.h>
using namespace std;
typedef struct IN
{
int a;
int b;
int c;
}IN;
IN s[];
int N,M;
int pre[];
int cmp(const void *a,const void *b)
{
return (*(IN *)a).c - (*(IN *)b).c;
}
int find(int x)
{
int i,r,t;
r=x;
while(r!=pre[r])
r=pre[r];
while(x!=r)
{
i=pre[x];
pre[x]=r;
x=i;
}
return r;
}
int kruskal()
{
int i,j,pa,pb,num=,sum=;
for(i=;i<=M;i++)
pre[i]=i;
for(i=;i<N;i++)
{
pa=find(s[i].a);
pb=find(s[i].b);
if(pa!=pb)
{
pre[pa]=pb;
sum+=s[i].c;
num++;
}
}
if(num==M-)
return sum;
else
return ;
}
int main()
{
while(scanf("%d %d",&N,&M),N)
{
int i,j,t;
memset(s,,sizeof(s));
for(i=;i<N;i++)
scanf("%d %d %d",&s[i].a,&s[i].b,&s[i].c);
qsort(s,N,sizeof(s[]),cmp);
//for(i=0;i<N;i++)
//printf("%d\n",s[i].c);
t=kruskal();
if(t)
printf("%d\n",t);
else
printf("?\n");
}
return ;
}
最新文章
- SQL Server 2008 R2企业版开发版等版本下载 (转载)
- 关于FluentNhibernate数据库连接配置,请教
- 将某个Qt4项目升级到Qt5遇到的问题[转]
- Bootstrap表单布局样式
- Double-checked locking and the Singleton pattern--双重检查加锁失效原因剖析
- C# 玩家昵称屏蔽敏感字眼
- list和数组之间相互的转化
- 使用DBUtils小框架
- HDU 4916 Count on the path
- JSP学习(一)之中文乱码问题的解决
- Spring AOP 的proxy详解
- 2017-2018-1 20155306 mypwd的实现
- 阿里巴巴Java开发程序猿年薪40W是什么水平?
- react-native-router-flux
- redis底层设计(二)——内存映射数据结构
- 在Windows系统配置Jekyll
- 吴裕雄 14-MySQL DELETE 语句
- 解决com.microsoft.sqlserver.jdbc.SQLServerException: 该连接已关闭
- 令人血脉喷张的animate.css
- 设计与实现分离——面向接口编程(OO博客第三弹)
热门文章
- ubuntu 16.04 Hbase 安装
- 如何在vue项目中引入阿里巴巴的iconfont图库
- Network(Tarjan+LCA)
- POJ3687Labeling Balls
- [Swift通天遁地]五、高级扩展-(4)快速生成Invert、Mix、Tint、Shade颜色及调整饱和度阶
- MyBatis Generator实现MySQL分页插件
- C/C++ Python的函数默认参数
- Linq学习(三)-基本查询
- 6.11---字节输入流数据根据字节输出流存到文件中---io流概念及分类---文件存储的原理和记事本打开的原理---字节流读取文件的原理---文件复制的原理
- Laravel5.1学习笔记20 EloquentORM 关系