poj 2349 uva 10369 - Arctic Network

点击打开链接uva 10369

1题目意思：

某地有s颗卫星，有p个站点，s<p。现在两个站点之间可以靠卫星和无线电相连，如果是依靠卫星相连的 。那么两个站点的距离可以无限大。如果是依靠无线电先相连的那么两个站点的距离D越大那么费用越高。题目要求在利用完s个卫星后，剩下的利用无线电相连的时候求出最小的D值

2思路：最小生成树+第k大的边

3分析：
1利用Prime算法，把最小生成数的边存储在ans数组里面，最后对ans按照从大到小排序，最后的ans就是ans[n-1].
2由上面我们知道通过卫星相连的站点的距离可以很大，那么我们通过最小生成树求出来的最大的权值的边就可以当成是卫星来连接的，排序后那么扣除n条边，那么最后的ans就是ans[n-1];

4代码：

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define MAXN 1010
#define INF 0xFFFFFFF

int t , s , p , cnt;
double ans[MAXN];
double G[MAXN][MAXN];
double lowcost[MAXN];
int vis[MAXN];
struct Point{
     double x;
     double y;
}point[MAXN];

bool cmp(double x , double y){
     return (x-y) > 1e-9;
}

void init(){
     for(int i = 1 ; i <= p ; i++){
        for(int j = 1 ; j <= p ; j++){
           double tmp_x = (point[i].x-point[j].x)*(point[i].x-point[j].x);
           double tmp_y = (point[i].y-point[j].y)*(point[i].y-point[j].y);
           G[i][j] = sqrt(tmp_x + tmp_y);
        }
     }
}

void Prime(){
     int pos;
     double min;
     memset(vis , 0 , sizeof(vis));
     memset(ans , 0 , sizeof(ans));
     vis[1] = 1;
     init();
     cnt = 0;
     for(int i = 1 ; i <= p ; i++)
        lowcost[i] = G[1][i];
     for(int i = 1 ; i <= p ; i++){
        min = INF;
        for(int j = 1 ; j <= p ; j++){
           if(!vis[j] && min-lowcost[j] > 1e-9){
              min = lowcost[j];
              pos = j;
           }
        }
        if(min == INF)
           break;
        ans[cnt++] = min;
        vis[pos] = 1;
        for(int j = 1 ; j <= p ; j++){
           if(!vis[j] && lowcost[j]-G[pos][j] > 1e-9)
             lowcost[j] = G[pos][j];
        }
     }
     sort(ans , ans+cnt , cmp);
     printf("%0.2lf\n" , ans[s-1]);
}

int main(){
   // freopen("input.txt" , "r" , stdin);
    scanf("%d" , &t);
    while(t--){
        scanf("%d%d" , &s , &p);
        for(int i = 1 ; i <= p ; i++)
           scanf("%lf%lf" , &point[i].x , &point[i].y);
        Prime();
    }
    return 0;
}