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 阅读(468) 评论(2)  编辑 收藏 引用 所属分类: ACM 、Algorithm 、课内作业

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  回复  更多评论   



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理