• <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精品久久久久久秒播| 久久人人爽人人爽人人AV| 国产精品久久久久久久久鸭| 久久夜色精品国产噜噜麻豆| 麻豆精品久久久一区二区| 热综合一本伊人久久精品| 中文字幕乱码久久午夜| 久久99精品国产麻豆宅宅 | 日产精品久久久久久久| 久久丫精品国产亚洲av| 久久无码一区二区三区少妇 | 久久精品国产日本波多野结衣| 久久久久久国产精品无码超碰| 久久精品国产只有精品66| 18岁日韩内射颜射午夜久久成人| 亚洲国产天堂久久综合网站| 久久精品国产亚洲AV忘忧草18| www亚洲欲色成人久久精品| 99久久精品免费看国产一区二区三区| 久久精品www| 欧美黑人激情性久久| 亚洲国产成人久久笫一页| 99国内精品久久久久久久| 精品永久久福利一区二区| 久久亚洲国产成人影院| 国产精品热久久毛片| 成人国内精品久久久久影院| 亚洲成色WWW久久网站| 久久这里只精品99re66| 亚洲欧美日韩精品久久亚洲区| 久久精品国产黑森林| 精品久久久无码中文字幕天天| 精品久久久久久| 久久福利青草精品资源站| 潮喷大喷水系列无码久久精品| 午夜精品久久久久久99热| 久久久久久久波多野结衣高潮| 人妻无码精品久久亚瑟影视| 亚洲精品无码专区久久同性男| 亚洲午夜无码AV毛片久久| 久久精品免费一区二区|