PKU 2349 Arctic Network
http://poj.org/problem?id=2349
久しぶりのPKU。
tcとかcfのレーティングが全然上がる気配を見せないので、悲しいです。
二次元平面上にP個のノードがあって、そのうちSのノードは衛生通信ができるようになっている。衛生通信は衛星通信ができるノード同士でしか使うことができない。
それ以外のノード間通信は無線で行われる。
衛星通信できるノードをうまく割り当てて、(直接的又は、間接的に)無線通信をしなければならない最大距離を最低にしろというような問題。
最小全域木+α的問題。
最小全域木に使われる辺のうち短いものからp-s個目の長さが無線通信の最大距離になる。
int cost[1000]; int p; PI in[1000]; int un[1000]; int find(int x){ if(x==un[x])return x; return un[x]=find(un[x]); } int unit(int a,int b){ un[find(a)]=find(b); } void solve(){ int s,p; cin>>s>>p; priority_queue<pair<int,PI> >q; rep(i,p){ un[i]=i; cin>>in[i].F>>in[i].S; rep(j,i){ int x=in[i].F-in[j].F; int y=in[i].S-in[j].S; q.push(mp(-x*x-y*y,mp(i,j))); } } p=0; while(!q.empty()){ int c=-q.top().F; int i=q.top().S.F; int j=q.top().S.S; q.pop(); if(find(i)==find(j))continue; cost[p++]=c; unit(i,j); } printf("%.2f\n",sqrt(cost[p-s])); } main(){ int n; cin>>n; while(n--)solve(); }