(UVA) 11228 - Transportation system [Prim的Minimum Spanning Tree]

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

解題關鍵：MST

這次改用Prim演算法，複雜度O(n^2)，在rank排名竟然達到第10名！！！

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

typedef pair<double,double> pdd;
const int MAX_N = 1004;
const int MAX_R = 40005;
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!
int state;

pdd Prim(int n,double r) {
 state=0;
 double ans1=0.0,ans2=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;
  if (dis(v[p],v[parent[p]]) <= r) ans1+=dis(v[p],v[parent[p]]);
  else ans2+= dis(v[p],v[parent[p]]),state++;
//  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;
   }
  }
 }
 return make_pair(ans1,ans2);
}

int main () {
 int T;
 scanf("%d",&T);
 for (int qq=0;T>qq;qq++) {
  int n;
  double r;
  scanf("%d %lf",&n,&r);
  for (int x=0;n>x;x++) {
   int i,j;
   scanf("%d %d",&i,&j);
   v[x]=make_pair(i,j);
  }
  pdd ret=Prim(n,r);
  printf("Case #%d: %d %.0f %.0f\n",qq+1,state+1,ret.first,ret.second);
 }
}

/*
3
3 100
0 0
1 0
2 0
3 1
0 0
100 0
200 0
4 20
0 0
40 30
30 30
10 10

*/