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

            亚洲国产成人久久综合碰碰动漫3d| 国产99精品久久| 精品久久久久久国产牛牛app | 91精品久久久久久无码| 人妻无码精品久久亚瑟影视| 久久精品国产亚洲AV无码娇色| 精品无码久久久久久久久久| 色婷婷噜噜久久国产精品12p| 久久精品国产亚洲av麻豆色欲 | 热久久这里只有精品| 亚洲中文精品久久久久久不卡| 久久综合九色综合97_久久久| 久久国产视屏| 国产亚州精品女人久久久久久 | 久久成人18免费网站| 无码人妻精品一区二区三区久久久| 久久露脸国产精品| 伊人久久大香线蕉影院95| 狠狠色丁香久久婷婷综合蜜芽五月| 国产日韩久久久精品影院首页 | 97香蕉久久夜色精品国产 | 久久亚洲精品中文字幕| 国产综合成人久久大片91| 97精品伊人久久久大香线蕉| 久久国产影院| 91久久香蕉国产熟女线看| 99久久人妻无码精品系列蜜桃| 久久久久人妻精品一区二区三区 | 久久妇女高潮几次MBA| 精品久久久无码人妻中文字幕| 久久国产精品二国产精品| 久久精品欧美日韩精品| 久久亚洲精品成人AV| 亚洲精品无码久久久久去q| 亚洲午夜久久久久久久久电影网| 亚洲&#228;v永久无码精品天堂久久 | 久久久久久亚洲AV无码专区| 日本强好片久久久久久AAA| 亚洲国产精品一区二区久久hs| 777午夜精品久久av蜜臀| 精品国产乱码久久久久久呢|