填充管道

发布时间:2017-3-23 16:14:39 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"填充管道",主要涉及到填充管道方面的内容,对于填充管道感兴趣的同学可以参考一下。

点击打开链接 Tunnels TimeLimit: 1 Second   MemoryLimit: 32 Megabyte Totalsubmit: 86   Accepted: 33   Description Water can flow around, does not it? And it can also flow along a tunnel until it become stable. A certain amount of water could be held by some length of tunnel, so the amount of water in the tunnels is related to the length of tunnels. Here goes the problem that you are given some coordinates of vertexes. All you have to do is to connect all the vertexes with tunnels, can you find a way to connect all these vertexes so that the mount of water in these tunnels is minimized. Input The input contains multiple cases. Ease case begins with a line with an integer N (0<=N<=100), which is the number of vertexes you need to connect. The next N lines each contains two real numbers, the coordinates of vertexes. N=0 indicates the end of input. Output For each test case print the minimum of water you need, rounded to 2 decimal places. Sample Input 5 0 0 0 3 2 1 1 1 2.5 3.7 0 Sample Output 7.25 用普里姆或者克鲁斯卡尔(破圈法)。 #include<stdio.h> #include<string.h> #include<math.h> #define MAXN 101 const double INF = 10000000.0; double mat[MAXN][MAXN]; int n; double prim(){ double min[MAXN]; double ret = 0; int v[MAXN]; int i,j,k; for(i=0;i<n;i++) { min[i] = INF; v[i] = 0; } min[0] = 0; for(j=0;j<n;j++){ for(k = -1,i=0;i<n;i++){ if(!v[i] && (k==-1 || min[i]<min[k])) k = i; } v[k] = 1; ret += min[k]; for(i=0;i<n;i++){ if(!v[i] && mat[k][i]<min[i]) min[i] = mat[k][i]; } } return ret; } int main(){ int i,j,k; double x[101],y[101],res; while(scanf("%d",&n)!=EOF,n){ for(i=0;i<n;i++){ scanf("%lf%lf",&x[i],&y[i]); } for(i=0;i<n;i++){ for(j=i+1;j<n;j++){ mat[i][j] = mat[j][i] = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j])); } } res = prim(); printf("%.2lf\n",res); } return 0; }

上一篇:C++ Primer读书笔记【chapter 1】
下一篇:linux下ssh远程登录/scp远程复制文件/rsync远程同步命令的自动登录

相关文章

关键词: 填充管道

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款