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

题意:

给定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[], Y[], dis[];
vector<int> G[];
bool vis[];
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+, inf);
mem(vis,);
vis[] = ;
dis[] = ;
for(int i = ; i < G[].size(); i++){
int v = G[][i];
dis[v] = p2p(X[], Y[], X[v], Y[v]);
}
vector<double> ans;
set<int> in;
rep(times, , p-){
double min_dis = 1e9;
int pick = -;
_rep(i,,p){
if(!vis[i] && dis[i] < min_dis){
min_dis = dis[i], pick = i;
}
}
vis[pick] = ;
ans.push_back(min_dis);
// printf("min_dis : %.4f\n", min_dis);
rep(i,,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, 那么不能减少任意一条边
printf("%.2f\n", ans[ans.size() - ]);
return;
}
if(p - s - >= ans.size()) { //如果s - 1多于边的总数, 那么不用任何一条边
puts("");
}
else printf("%.2f\n", ans[p-s-]); //找出第s-1大的边 }
int main(){
cin >> T;
while(T--){
cin >> s >> p;
_rep(i,,p){
double x, y;
cin >> x >> y;
X[i] = x, Y[i] = y;
}
_rep(i,,p)_rep(j,i+,p){ //建一个完全图, 因为任意两点都是可达的
G[i].push_back(j);
G[j].push_back(i);
}
prim();
_rep(i,,p) G[i].clear();
mem(vis,);
mem(X,);
mem(Y,);
}
return ;
}
上一篇:Android weight属性详解


下一篇:App推荐 | Google Tasks