HDU_1233_还是畅通工程
还是畅通工程
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 28842 Accepted Submission(s): 12893
当N为0时,输入结束,该用例不被处理。
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
代码:
#include<stdio.h>
struct path
{
int a; //a地
int b; //b地
int fee; //距离
};
struct path num[10000];
int father[10000],sum;
void sort(struct path num[],int n) //排序
{
struct path term;
int i,j,flag;
for(i=0; i<n; i++)
{
flag=i;
for(j=i+1; j<n; j++)
if(num[j].fee<num[flag].fee)
flag=j;
term=num[i];
num[i]=num[flag];
num[flag]=term;
}
}
int find(int a)
{
if(father[a]!=a)
father[a]=find(father[a]);
return father[a];
}
void merge(struct path pre)
{
int x,y;
x=find(pre.a);
y=find(pre.b);
if(x!=y)
{
father[x]=y;
sum+=pre.fee;
}
}
int main()
{
int n,i;
while(1)
{
scanf("%d",&n);
if(n==0)
break;
for(i=1; i<=n; i++)
father[i]=i;
for(i=0; i<n*(n-1)/2; i++)
scanf("%d%d%d",&num[i].a,&num[i].b,&num[i].fee);
sort(num,n*(n-1)/2);
sum=0;
for(i=0; i<n*(n-1)/2; i++)
merge(num[i]);
printf("%d\n",sum);
}
return 0;
}
最新文章
- drawable微技巧以及layout的小知识
- VisualStudio控制台输出窗口一闪而过
- 浅谈html5及其新特性
- 关于sizeof 跟strlen 的区别
- web进阶之jQuery操作DOM元素&;&;MySQL记录操作&;&;PHP面向对象学习笔记
- Windows Platform Predefined Macros
- Git subtree和Git submodule
- php getenv 和 putenv 用法
- python学习(序章)
- c#操作MySQL数据库中文出现乱码(很多问号)的解决方法
- Treap的读书笔记2
- Thinkphp入门三—框架模板、变量(47)
- 2018-2019-2 网络对抗技术 20165319 Exp3 免杀原理与实践
- .NET 内存分配笔记
- 语音识别传统方法(GMM+HMM+NGRAM)概述
- 剑指offer——python【第28题】数组 中出现次数超过一半的数字
- android -------- 颜色的半透明效果配置
- HDU.4035.Maze(期望DP)
- go post 上传文件的例子
- RDLC_部署到不同的浏览器
热门文章
- 字符串处理(正则表达式、NSScanner扫描、CoreParse解析器)-b
- tf.image.resize_bilinear 图像缩放,双线性插值-图像中心对齐
- UVA 11488 Hyper Prefix Sets (Trie)
- android:模拟水波效果的自己定义View
- ios32---线程的状态
- ios25---图片拉伸
- 【OI新闻】2016.10.06
- not syncing : corrupted stack end detected inside scheduler
- mysql status关键字 数据表设计中慎重使用
- 7章 Admin