首页 > Web开发 > 详细

POJ 2349 Arctic Network(贪心 最小生成树)

时间:2018-01-21 22:00:39      阅读:187      评论:0      收藏:0      [点我收藏+]

题意:

给定n个点, 要求修p-1条路使其连通, 但是现在有s个卫星, 每两个卫星可以免费构成连通(意思是不需要修路了), 问修的路最长距离是多少。

分析:

s个卫星可以代替s-1条路, 所以只要求最小生成树, 排序后后去掉s-1条边, 最大那条就是答案。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include <iomanip>
#define rep(i,a,b) for(int i = a; i < b; i++)
#define _rep(i,a,b) for(int i = a; i <= b; i++)
#define mem(a,n) memset(a,n,sizeof(a))
#define fre(a) freopen(a,"r", stdin);

typedef long long LL;
using namespace std;
const double inf = 1e9;
int T,s,p;
double p2p(double x1, double y1, double x2, double y2){ //距离可以需要时候再求出来
    return sqrt((x1-x2) * (x1-x2) + (y1-y2)*(y1-y2));
}
double X[567], Y[567], dis[567];
vector<int> G[567];
bool vis[567];
struct edge{
    int u ,v;
    double d;
    edge(int _u,int  _v, double _d):u(_u),v(_v),d (_d){};
};
bool cmp(edge a, edge b){
    return a.d > b.d;
}
void prim(){
    fill(dis, dis+567, inf);
    mem(vis,0);
    vis[1] = 1;
    dis[1] = 0;
    for(int i = 0; i < G[1].size(); i++){
        int v = G[1][i];
        dis[v] = p2p(X[1], Y[1], X[v], Y[v]);
    }
    vector<double> ans;
    set<int> in;
    rep(times, 0, p-1){
        double min_dis = 1e9;
        int pick = -1;
        _rep(i,1,p){
            if(!vis[i] && dis[i] < min_dis){
                min_dis = dis[i], pick = i;
            }
        }
        vis[pick] = 1;
        ans.push_back(min_dis);
//        printf("min_dis : %.4f\n", min_dis);
        rep(i,0,G[pick].size()){
            int v = G[pick][i];
            double d = p2p(X[pick], Y[pick], X[v], Y[v]);
            if(dis[v] > d) dis[v] = d;
        }
    }

    sort(ans.begin(), ans.end());

    if(s < 2){//如果小于2, 那么不能减少任意一条边
        printf("%.2f\n", ans[ans.size() - 1]);
        return;
    }
    if(p - s - 1 >= ans.size()) { //如果s - 1多于边的总数, 那么不用任何一条边
        puts("0");
    }
    else printf("%.2f\n", ans[p-s-1]); //找出第s-1大的边


}
int main(){
    cin >> T;
    while(T--){
        cin >> s >> p;
        _rep(i,1,p){
            double x, y;
            cin >> x >> y;
            X[i] = x, Y[i] = y;
        }
        _rep(i,1,p)_rep(j,i+1,p){ //建一个完全图, 因为任意两点都是可达的
            G[i].push_back(j);
            G[j].push_back(i);
        }
        prim();
        _rep(i,1,p) G[i].clear();
        mem(vis,0);
        mem(X,0);
        mem(Y,0);
    }
    return 0;
}

 

 

POJ 2349 Arctic Network(贪心 最小生成树)

原文:https://www.cnblogs.com/Jadon97/p/8325494.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!