(UVA) 10369 - Arctic Network

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=1310

題意：有p個點，其中要給一個樹，使得兩兩點可以直接 or 間接連通。其中，你可以在s個點設置衛星，任兩個衛星連線，cost會視為0。

那可以想像的事說，先找MST，把cost丟到一個max heap裡面。之後你有s個衛星，那就等於免費奉送s-1個邊。因此，再把MST前s-1個邊pop完後，就是答案XD。

(因為code有一部分是貼上一份code，所以縮排有點亂QQ)

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <queue>
using namespace std;

typedef pair<double,double> pdd;
const int MAX_N = 503;
const double INF = 1e9+7;

inline double dis(pdd a,pdd b) {
 return sqrt((a.first-b.first)*(a.first-b.first) + (a.second-b.second)*(a.second-b.second));
}

double d[MAX_N];
pdd v[MAX_N];
bool visit[MAX_N];
int parent[MAX_N];  //to collect edge, we need that!

double Prim(int n,int m) {
priority_queue<double> que;

double mx=0.0;

 for (int x=0;n>x;x++) {
  d[x] = 1e9+7;
  visit[x]=false;
 }

 d[0]=0.0;
 parent[0]=0;

 for (int x=0;n>x;x++) {
  double min=INF;
  int p;
  for (int y=0;n>y;y++) {
   if (visit[y]==false && d[y]<min) {
    p=y;
    min=d[y];
   }
  }
  //we select p
  visit[p]=true;
  que.push(dis(v[p],v[parent[p]]));
//  cout<<"get "<<p<<" & "<<parent[p]<<endl;
  for (int y=0;n>y;y++) {
   if (visit[y]==false && dis(v[p],v[y]) < d[y]) {
    d[y] = dis(v[p],v[y]);
    parent[y]=p;
   }
  }
 }
 for (int x=0;m-1>x;x++) que.pop();
 return que.top();
}

int main () {
 int T;
 scanf("%d",&T);
 for (int qq=0;T>qq;qq++) {
  int m,n;
  scanf("%d %d",&m,&n);
  for (int x=0;n>x;x++) {
   int i,j;
   scanf("%d %d",&i,&j);
   v[x]=make_pair(i,j);
  }
  printf("%.2f\n",Prim(n,m));
 }
}