coreBugZJ

此 blog 已弃。

EOJ 2067 Building Roads

  1/*
  2EOJ 2067 Building Roads
  3
  4
  5----题意:
  6二维平面中有 N 个点,其中 M 对点已经有边连接,
  7现在需要增加若干条边,以使所有点相互连通。
  8定义边的长度为两点间的欧几里得距离。
  9
 10求增加的边的总长度的最小值。
 11
 12
 13----输入:
 14第一行,两个空格分开的整数 N 和 M;
 15第二行到第N+1行,每行两个空格分开的整数 Xi 和 Yi,表示第 i 个点的坐标;
 16第N+2行到第N+M+2行,两个空格分开的整数 i 和 j,表示第 i 个点和第 j 个点之间已经有一条边。
 17
 18
 19----输出:
 20增加的边的总长度的最小值,保留两位小数。
 21
 22
 23----数据范围:
 241 <= N  <= 1,000
 251 <= M  <= 1,000
 260 <= Xi <= 1,000,000
 270 <= Yi <= 1,000,000
 28
 29
 30----样例输入:
 314 1
 321 1
 333 1
 342 3
 354 3
 361 4
 37
 38
 39----样例输出:
 404.00
 41
 42
 43----分析:
 44类似最小生成树模型,只是含有已经存在的边。
 45
 46
 47----结论:
 48定义图论模型,两点间的距离为两点间的欧几里得距离,
 49然后,将已经存在的边的长度定义为零。
 50进行 Prime 算法求最小生成树。
 51
 52
 53*/

 54
 55
 56#include <stdio.h>
 57#include <math.h>
 58
 59#define  L  1003
 60
 61int n, x[ L ], y[ L ];
 62double  w[ L ][ L ];
 63
 64double minCost() {
 65        double MM = 1e100;
 66        double ans = 0, m, dist[ L ];
 67        int i, j, k, cnt[ L ];
 68        for ( i = 1; i <= n; ++i ) {
 69                dist[ i ] = MM;
 70                cnt[ i ]  = 0;
 71        }

 72        dist[ 1 ] = 0;
 73        for ( i = 1; i <= n; ++i ) {
 74                m = MM;
 75                for ( j = 1; j <= n; ++j ) {
 76                        if ( (! cnt[ j ]) && (m>dist[j]) ) {
 77                                m = dist[ k = j ];
 78                        }

 79                }

 80                ans += m;
 81                cnt[ k ] = 1;
 82                for ( j = 1; j <= n; ++j ) {
 83                        if ( (!cnt[j]) && (dist[j]>w[k][j]) ) {
 84                                dist[ j ] = w[ k ][ j ];
 85                        }

 86                }

 87        }

 88        return ans;
 89}

 90
 91int main() {
 92        int i, j, k;
 93        scanf( "%d%d"&n, &k );
 94        for ( i = 1; i <= n; ++i )
 95                scanf( "%d%d", x + i, y + i );
 96        for ( i = 1; i < n; ++i )
 97                for ( j = i; j <= n; ++j ) {
 98                        w[ i ][ j ] = w[ j ][ i ] =sqrt( (double)(x[i]-x[j]) * (x[i]-x[j]) + (double)(y[i]-y[j]) * (y[i]-y[j])  );
 99                }

100        while ( k-- ) {
101                scanf( "%d%d"&i, &j );
102                w[ i ][ j ] = w[ j ][ i ] = 0;
103        }

104        printf( "%0.2lf\n", minCost() );
105        return 0;
106}

107

posted on 2012-03-04 22:37 coreBugZJ 阅读(355) 评论(2)  编辑 收藏 引用 所属分类: ACMAlgorithm课内作业

Feedback

# re: EOJ 2067 Building Roads 2012-03-16 10:18 C小加

EOJ是哪里?  回复  更多评论   

# re: EOJ 2067 Building Roads 2012-03-16 19:42 coreBugZJ

@C小加
Ecnu Online Judge
http://acm.cs.ecnu.edu.cn/index.php  回复  更多评论   



只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理