• <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>
            

    
            

            




            







												


        


            


            coreBugZJ
            

            此 blog 已棄。
            

            




            
	
					
	
            
		
            
			EOJ 2067 Building Roads
		
            
		
              1/*
              2EOJ 2067 Building Roads
              3
              4
              5----題意：
              6二維平面中有 N 個(gè)點(diǎn)，其中 M 對(duì)點(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 閱讀(486) 評(píng)論(2)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    


            

            Feedback
            
	
	
			
            
				# re: EOJ 2067 Building Roads
					
						2012-03-16 10:18
					
				C小加
			
            
			
            
				EOJ是哪里？  回復(fù)  更多評(píng)論
				  
				
			
            
		
			
            
				# re: EOJ 2067 Building Roads
					
						2012-03-16 19:42
					
				coreBugZJ
			
            
			
            
				@C小加

            Ecnu Online Judge

            http://acm.cs.ecnu.edu.cn/index.php  回復(fù)  更多評(píng)論
				  
				
			
            
		

            

            




            






            

				

            


    
    







            
	   
	



亚洲狠狠婷婷综合久久蜜芽|
99久久综合狠狠综合久久止|
国产高潮久久免费观看|
曰曰摸天天摸人人看久久久|
久久99热这里只有精品国产|
久久国产色av免费看|
久久天堂AV综合合色蜜桃网|
国产成人无码精品久久久免费
|
久久亚洲精品国产亚洲老地址|
无码国内精品久久人妻|
色综合合久久天天综合绕视看|
亚洲国产精品嫩草影院久久|
国内精品伊人久久久久|
深夜久久AAAAA级毛片免费看|
久久午夜伦鲁片免费无码|
久久久久亚洲精品无码网址|
久久精品亚洲精品国产色婷|
久久人人爽人爽人人爽av|
九九久久自然熟的香蕉图片|
欧美黑人激情性久久|
99久久精品国产综合一区|
色欲综合久久中文字幕网|
久久99精品国产麻豆不卡|
国产成人无码久久久精品一|
久久伊人中文无码|
中文字幕亚洲综合久久2|
亚洲综合熟女久久久30p|
亚洲国产精品无码久久青草|
色综合久久最新中文字幕|
国内精品九九久久久精品|
久久强奷乱码老熟女网站|
亚洲欧美国产日韩综合久久|
精品国产乱码久久久久久浪潮|
狠色狠色狠狠色综合久久|
麻豆AV一区二区三区久久|
色综合久久综合中文综合网|
久久精品综合网|
噜噜噜色噜噜噜久久|
久久中文字幕人妻熟av女|
国産精品久久久久久久|
国产精品欧美久久久久天天影视|