POJ 2349 Arctic Network

题目链接：kuangbin带你飞 专题六 最小生成树 G - Arctic Network

题意

n个前哨，s个卫星频道。任意两个前哨可以通过卫星频道或者无线电来通信，前者无视距离，后者最大距离为d，与无线电装置的能量相关。每个前哨的无线电能量都相同，问在所有前哨都可以直接或间接通信的情况下，最小的d是多少

思路

显然，此题是最小生成树问题。特殊的是，有s个卫星频道可以无视距离。
将n前哨的最小生成树求出并对n-1条边排序，后s-1条边使用卫星，那么剩余边中最大的边长即为所求的d。
问题也就可以转化为求最小生成树第k大边问题，在本题是，求第n－s大边的问题。

代码

//
//  main.cpp
//  demo
//
//  Created by shiyi－mac on 16/1/2.
//  Copyright © 2016年 shiyi－mac. All rights reserved.
//
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

const int N = 509;
const int MAX = 1000000;
double g[N][N];
double d[N], p[N];
int x[N], y[N];

double prim(int s, int n)
{
    for(int i=2;i<=n;i++)
        d[i] = g[1][i];
    d[1] = -1;
    for(int i=1;i<n;i++)
    {
        double min = MAX;
        int imin = -1;
        for(int j=1;j<=n;j++)
            if(d[j]!=-1 && min > d[j])
                min = d[j], imin = j;
        p[i] = min;
        //cout<<min<<endl;
        d[imin] = -1;
        for(int j=1;j<=n;j++)
            if(d[j]!=-1 && d[j] > g[imin][j])
                d[j] = g[imin][j];
    }
    sort(p+1, p+n);
    return p[n-s];
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int s, p;
        scanf("%d%d",&s, &p);
        for(int i=1;i<=p;i++)
            scanf("%d%d",&x[i], &y[i]);
        for(int i=1;i<=p;i++)
            for(int j=i+1;j<=p;j++)
            {
                double l = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
                g[j][i] = g[i][j] = l;
            }
        printf("%.2f\n", prim(s, p));
    }
    return 0;
}