Description
Input
Output
Sample Input
1 2 4 0 100 0 300 0 600 150 750
Sample Output
212.13
题意:
可以这么理解:有S个卫星可以免费通信,相当于有S-1条权值为0的边,然后剩下求出剩下权值最大的一条边。
题解:
当然是最小生成树里最大的m-1条边权值设为0,然后记录剩下最大的那条边的权值就好了。
#include<iostream> #include<cmath> #include<algorithm> using namespace std; const int maxn=505; int par[maxn]; int n,m; int cas; struct edge { int u,v; double cost; }es[maxn*maxn]; struct node { int x,y; }p[maxn]; double dis(node a,node b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } bool cmp(edge a,edge b) { return a.cost<b.cost; } void init() { for(int i=1;i<=n;i++) par[i]=i; } int find(int x) { return x==par[x]?x:par[x]=find(par[x]); } void unite(int x,int y) { x=find(x); y=find(y); if(x!=y) par[x]=y; } bool same(int x,int y) { return find(x)==find(y); } double kruskal() { init(); sort(es,es+cas,cmp); int cnt=0; for(int i=0;i<cas;i++) { edge e=es[i]; if(!same(e.u,e.v)) { unite(e.u,e.v); if(++cnt==n-m) return e.cost; } } return 0; } int main() { int t; cin>>t; while(t--) { cin>>m>>n; for(int i=0;i<n;i++) cin>>p[i].x>>p[i].y; cas=0; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) { double d=dis(p[i],p[j]); es[cas].u=i+1,es[cas].v=j+1; es[cas].cost=d; cas++; } printf("%.2lf\n",kruskal()); } return 0; }
POJ 2349 Arctic Network (最小生成树)
原文:http://www.cnblogs.com/orion7/p/7399820.html