青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

此 blog 已棄。

EOJ 2067 Building Roads

  1/*
  2EOJ 2067 Building Roads
  3
  4
  5----題意:
  6二維平面中有 N 個(gè)點(diǎn),其中 M 對點(diǎn)已經(jīng)有邊連接,
  7現(xiàn)在需要增加若干條邊,以使所有點(diǎn)相互連通。
  8定義邊的長度為兩點(diǎn)間的歐幾里得距離。
  9
 10求增加的邊的總長度的最小值。
 11
 12
 13----輸入:
 14第一行,兩個(gè)空格分開的整數(shù) N 和 M;
 15第二行到第N+1行,每行兩個(gè)空格分開的整數(shù) Xi 和 Yi,表示第 i 個(gè)點(diǎn)的坐標(biāo);
 16第N+2行到第N+M+2行,兩個(gè)空格分開的整數(shù) i 和 j,表示第 i 個(gè)點(diǎn)和第 j 個(gè)點(diǎn)之間已經(jīng)有一條邊。
 17
 18
 19----輸出:
 20增加的邊的總長度的最小值,保留兩位小數(shù)。
 21
 22
 23----數(shù)據(jù)范圍:
 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類似最小生成樹模型,只是含有已經(jīng)存在的邊。
 45
 46
 47----結(jié)論:
 48定義圖論模型,兩點(diǎn)間的距離為兩點(diǎn)間的歐幾里得距離,
 49然后,將已經(jīng)存在的邊的長度定義為零。
 50進(jìn)行 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 閱讀(512) 評論(2)  編輯 收藏 引用 所屬分類: ACMAlgorithm課內(nèi)作業(yè)

Feedback

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

EOJ是哪里?  回復(fù)  更多評論   

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

@C小加
Ecnu Online Judge
http://acm.cs.ecnu.edu.cn/index.php  回復(fù)  更多評論   


青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            91久久在线视频| 久久国产欧美日韩精品| 亚洲伦理精品| 在线观看亚洲| 好吊视频一区二区三区四区 | 久久久www成人免费无遮挡大片| 亚洲精品国产精品国自产在线 | 亚洲一区成人| 亚洲——在线| 欧美一区二区三区喷汁尤物| 亚洲欧美电影在线观看| 欧美亚洲日本网站| 久久久久国产精品www| 久久久国产亚洲精品| 久久伊人一区二区| 欧美黄色小视频| 亚洲毛片一区| 亚洲午夜一区二区三区| 性久久久久久久久| 久久夜色精品| 欧美日韩国产在线看| 国产精品久久久久久久久久免费 | 欧美一区午夜精品| 久久久噜噜噜久久中文字幕色伊伊| 欧美一区二区三区四区高清| 久久久97精品| 亚洲国产欧美国产综合一区| 艳女tv在线观看国产一区| 亚洲男人av电影| 另类图片国产| 国产精品久久久亚洲一区| 国产无遮挡一区二区三区毛片日本| 国产有码一区二区| 一区二区免费在线播放| 久久久久成人网| 亚洲最新在线| 欧美jjzz| 国产在线乱码一区二区三区| aa日韩免费精品视频一| 久久精品亚洲乱码伦伦中文 | 久久综合狠狠综合久久综合88| 欧美国产精品中文字幕| 国产热re99久久6国产精品| 亚洲美女淫视频| 久久久精品日韩欧美| 国产精品进线69影院| 亚洲精品乱码久久久久| 久久久久久免费| 亚洲一区黄色| 久热精品在线视频| 亚洲无线视频| 欧美精品免费在线观看| 精品成人一区二区三区四区| 亚洲欧美日韩国产综合在线| 91久久精品美女| 久久亚洲私人国产精品va媚药| 国产精品国产三级国产| 日韩一二在线观看| 欧美岛国在线观看| 久久精品99无色码中文字幕| 亚洲狼人综合| 欧美激情一区二区三区全黄| 在线看国产一区| 榴莲视频成人在线观看| 欧美一区二区三区视频| 国产精品视频你懂的| 亚洲无线视频| 亚洲精品国产无天堂网2021| 免费中文字幕日韩欧美| 亚洲国产另类久久精品| 免费成人高清| 久久久亚洲人| 亚洲大片免费看| 免费看黄裸体一级大秀欧美| 日韩一区二区精品视频| 日韩视频第一页| 日韩午夜一区| 亚洲九九九在线观看| 欧美伦理a级免费电影| 日韩系列欧美系列| 99re8这里有精品热视频免费 | 日韩午夜激情av| 亚洲黄色性网站| 欧美日韩国产区一| 亚洲一区二区免费| 制服丝袜亚洲播放| 国产欧美日韩一区二区三区在线| 欧美在线日韩精品| 久久免费黄色| 日韩午夜激情| 香蕉成人伊视频在线观看| 伊人久久综合97精品| 91久久精品一区| 国产精品美女久久久久久2018 | 亚洲国产老妈| 欧美日韩激情小视频| 午夜免费在线观看精品视频| 欧美一区二区三区四区在线观看地址| 国产一区在线视频| 亚洲欧洲偷拍精品| 国产欧美激情| 亚洲黄色av一区| 国产毛片精品视频| 欧美激情在线观看| 国产精品美女999| 欧美激情视频在线免费观看 欧美视频免费一| 欧美精品日韩一区| 久久青草欧美一区二区三区| 欧美成人小视频| 欧美在线观看网站| 欧美黄色一区| 久久久天天操| 国产精品s色| 欧美大胆成人| 国产精品私房写真福利视频| 欧美电影电视剧在线观看| 国产精品国产精品| 欧美激情网友自拍| 国产一区自拍视频| 亚洲一区在线免费| 一二三四社区欧美黄| 久久久精品tv| 午夜精彩国产免费不卡不顿大片| 蜜臀va亚洲va欧美va天堂| 欧美在线观看天堂一区二区三区| 欧美日本在线播放| 欧美国产一区二区| 一区在线视频观看| 欧美亚洲一级片| 亚洲尤物在线视频观看| 亚洲免费高清视频| 免费高清在线一区| 久久亚洲春色中文字幕久久久| 国产精品福利久久久| 欧美一区二区黄色| 欧美gay视频| 国产视频在线观看一区| 99riav1国产精品视频| 亚洲第一中文字幕| 久久国产精品久久w女人spa| 午夜精品婷婷| 欧美午夜免费| 99精品国产在热久久婷婷| 日韩视频一区二区在线观看 | 日韩一区二区精品在线观看| 日韩亚洲一区二区| 欧美韩日亚洲| 亚洲精品乱码久久久久久蜜桃91| 亚洲日韩成人| 欧美日韩国产综合视频在线| 亚洲精品系列| 亚洲女同同性videoxma| 国产精品美女久久久久aⅴ国产馆| 亚洲一区二区三区视频| 久久高清国产| 亚洲国产99精品国自产| 欧美激情网站在线观看| 一区二区三区欧美亚洲| 久久久久.com| 99精品欧美一区二区三区 | 美女国产精品| 亚洲国产裸拍裸体视频在线观看乱了| 亚洲区第一页| 欧美日韩免费精品| 亚洲一级影院| 久久人人看视频| 亚洲欧洲精品天堂一级| 欧美日韩影院| 亚洲一区二区三区久久| 久久久久一区二区三区| 国产午夜精品久久久久久久| 午夜精品久久| 久久久青草婷婷精品综合日韩| 欧美日韩美女在线| 久久亚洲精品一区| 亚洲欧美日本国产专区一区| 欧美激情中文字幕一区二区| 久久美女性网| 亚洲综合第一| 欧美日韩亚洲一区二区三区四区| 欧美岛国激情| 亚洲国产精品女人久久久| 亚洲国产天堂久久国产91| 国产精品无码专区在线观看| 亚洲精品黄色| 99精品视频免费| 欧美精品一区二区三区蜜臀 | 亚洲欧洲在线免费| 久久婷婷麻豆| 久久综合伊人77777尤物| 亚洲综合第一页| 国产精品家教| 久久综合伊人77777尤物| 亚洲欧美日韩成人高清在线一区| 欧美日韩亚洲一区二区三区| 亚洲欧美国产另类| 欧美日韩免费区域视频在线观看| 宅男噜噜噜66一区二区| 欧美日韩一区二区视频在线观看| 亚洲欧洲一级|