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

            Description

            The Department of National Defence (DND) wishes to connect several northern outposts by a wireless network. Two different communication technologies are to be used in establishing the network: every outpost will have a radio transceiver and some outposts will in addition have a satellite channel.
            Any two outposts with a satellite channel can communicate via the satellite, regardless of their location. Otherwise, two outposts can communicate by radio only if the distance between them does not exceed D, which depends of the power of the transceivers. Higher power yields higher D but costs more. Due to purchasing and maintenance considerations, the transceivers at the outposts must be identical; that is, the value of D is the same for every pair of outposts.

            Your job is to determine the minimum D required for the transceivers. There must be at least one communication path (direct or indirect) between every pair of outposts.

            Input

            The first line of input contains N, the number of test cases. The first line of each test case contains 1 <= S <= 100, the number of satellite channels, and S < P <= 500, the number of outposts. P lines follow, giving the (x,y) coordinates of each outpost in km (coordinates are integers between 0 and 10,000).

            Output

            For each case, output should consist of a single line giving the minimum D required to connect the network. Output should be specified to 2 decimal points.

            Sample Input

            1 2 4 0 100 0 300 0 600 150 750 

            Sample Output

            212.13 

            Source


            #include<cstdio>
            #include
            <cstring>
            #include
            <iostream>
            #include
            <cmath>
            #include
            <algorithm>
            using namespace std;
            const int MAXN = 550;
            const double inf = 1e250;
            int m,n;
            double e[MAXN][MAXN],x[MAXN],y[MAXN],ord[MAXN],cost[MAXN];
            bool vi[MAXN];
            void prim(int s){
                
            for(int i=0;i<n;i++){
                    vi[i]
            =0;cost[i]=e[s][i];
                }
                vi[s]
            =1;cost[s]=0.0;ord[0]=0.0;
                
            int u=s;
                
            for(int i=1;i<n;i++){
                    ord[i]
            =inf;
                    
            for(int j=0;j<n;j++)
                        
            if(!vi[j] && cost[j]<ord[i])
                            ord[i]
            =cost[u=j];
                    vi[u]
            =1;
                    
            for(int j=0;j<n;j++)
                        
            if(!vi[j] && e[u][j]<cost[j])
                            cost[j]
            =e[u][j];
                }
                sort(ord,ord
            +n);
                printf(
            "%.2lf\n",ord[n-m]);
            }
            int main(){
                
            int t;
                scanf(
            "%d",&t);
                
            while(t--){
                    scanf(
            "%d%d",&m,&n);
                    
            for(int i=0;i<n;i++)
                        scanf(
            "%lf%lf",&x[i],&y[i]);
                    
            for(int i=0;i<n;i++)
                        
            for(int j=i+1;j<n;j++)
                            e[i][j]
            =e[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
                    prim(
            0);
                }
                
            return 0;
            }

            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            posts - 3, comments - 1, trackbacks - 0, articles - 16

            Copyright © lenohoo

            国产国产成人久久精品| 久久精品国产精品亚洲精品| 国产精品一久久香蕉国产线看| 狠狠色婷婷久久一区二区| 一本色道久久99一综合| 99久久精品费精品国产一区二区| 国产成人综合久久久久久| 成人a毛片久久免费播放| 伊人 久久 精品| 国产精品一区二区久久精品| 精品无码人妻久久久久久| 99久久无色码中文字幕人妻| 香蕉久久夜色精品国产小说| 无码国内精品久久综合88 | 日本久久久精品中文字幕| 国内精品久久久久影院网站 | 欧美国产精品久久高清| 中文字幕无码免费久久| 51久久夜色精品国产| 午夜精品久久久久久中宇| 51久久夜色精品国产| 一本久道久久综合狠狠爱| 国产亚州精品女人久久久久久 | 国产精品狼人久久久久影院| 欧美亚洲国产精品久久久久| 日韩精品久久久久久| 无码国内精品久久人妻蜜桃| 理论片午午伦夜理片久久| 日韩一区二区久久久久久| 精品久久久久久成人AV| 午夜精品久久久久久久| 久久精品免费全国观看国产| 久久久久久av无码免费看大片| 99久久99久久久精品齐齐 | 99久久婷婷国产一区二区| 久久免费的精品国产V∧| 亚洲伊人久久大香线蕉综合图片| 伊人久久大香线蕉综合网站| 久久无码一区二区三区少妇| 国产精品成人99久久久久91gav| 久久国产成人精品麻豆|