填充管道

发布时间:2016-12-7 3:49:43 编辑: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远程同步命令的自动登录

相关文章

关键词: 填充管道

相关评论