POJ 2349 Arctic Network
最小生成树第K小边问题。
题意是说有N个点,有两种连通方式,卫星和无线,卫星随意连通,无限需要配置接收器,接收器价格跟能接受的距离是一样的。
卫星频率是有限的,有M个频道。
也就是说组建最小生成树,前面 n-1-m 边用无线,后面m边用卫星。
用一个数组保存每次所需的代价,最后输出就好。
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<queue> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 using namespace std; int n,m; int fa[501]; struct lx { int u,v; double len; }l[501*250]; struct node { double x,y; }point[501]; int father(int x) { if(x!=fa[x]) fa[x]=father(fa[x]); return fa[x]; } bool cmp(lx a,lx b) { return a.len<b.len; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&m,&n); for(int i=0;i<=n;i++) fa[i]=i; for(int i=1;i<=n;i++) scanf("%lf%lf",&point[i].x,&point[i].y); int cot=0; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { l[cot].u=i; l[cot].v=j; l[cot++].len=sqrt(pow(point[i].x-point[j].x,2)+pow(point[i].y-point[j].y,2)); } sort(l,l+cot,cmp); double path[501]; int pcot=1; for(int i=0;i<cot;i++) { int fu=father(l[i].u); int fv=father(l[i].v); if(fu==fv)continue; fa[fv]=fu; path[pcot++]=l[i].len; } printf("%.2f\n",path[pcot-m]); } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。