POJ 2349 Arctic Network

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

](http://acm.hust.edu.cn/vjudge/contest/view.action?cid=66965#problem/G)

题意

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;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!