POJ 1751 - Highways

http://poj.org/problem?id=1751

概要

N 個の街があり，i 番目の街は座標 (x[i], y[i]) にある．

ある街と別の街を結ぶ高速道路が既に M 本ある．

最小のコストですべての街と街を行き来できるようにしたとき，新たに作る高速道路はどの街とどの街を結べばよいか答える．

ただし，コストは街と街のユークリッド距離とする．

また，新たに高速道路を作る必要が無いときは何も出力しない．

制約

解法

最小全域木を求めるだけ．

  1 #include <iostream>
  2 #include <vector>
  3 #include <algorithm>
  4 #include <cmath>
  5 using namespace std;
  6 
  7 struct DisjointSet/*{{{*/
  8 {
  9   vector<int> parent;
 10 
 11   int root(int x)
 12   {
 13     if (parent[x] < 0) {
 14       return x;
 15     } else {
 16       parent[x] = root(parent[x]);
 17       return parent[x];
 18     }
 19   }
 20 
 21   explicit DisjointSet(int n) : parent(n, -1) {}
 22 
 23   bool unite(int x, int y)
 24   {
 25     const int a = root(x);
 26     const int b = root(y);
 27     if (a != b) {
 28       if (parent[a] < parent[b]) {
 29         parent[a] += parent[b];
 30         parent[b] = a;
 31       } else {
 32         parent[b] += parent[a];
 33         parent[a] = b;
 34       }
 35       return true;
 36     } else {
 37       return false;
 38     }
 39   }
 40 
 41   bool find(int x, int y) { return root(x) == root(y); }
 42   int size(int x) { return -parent[root(x)]; }
 43 };/*}}}*/
 44 
 45 struct edge {/*{{{*/
 46   int u, v;
 47   typedef double weight_type;
 48   weight_type w;
 49   edge(int s, int d, weight_type w_) : u(s), v(d), w(w_) {}
 50   bool operator<(const edge& that) const { return w < that.w; }
 51 };/*}}}*/
 52 
 53 template <class Edge>
 54 vector<Edge> kruskal(const vector<Edge>& edges, DisjointSet& s)/*{{{*/
 55 {
 56   // assert(is_sorted(edges.begin(), edges.end()))
 57   const int N = s.parent.size();
 58   vector<Edge> ans;
 59   for (typename vector<Edge>::const_iterator it = edges.begin(); s.size(0) < N && it != edges.end(); ++it) {
 60     if (s.unite(it->u, it->v)) {
 61       ans.push_back(*it);
 62     }
 63   }
 64   return ans;
 65 }/*}}}*/
 66 
 67 inline double dist(const pair<int,int>& p, const pair<int,int>& q)
 68 {
 69   const double x = p.first - q.first;
 70   const double y = p.second - q.second;
 71   return sqrt(x*x + y*y);
 72 }
 73 
 74 int main()
 75 {
 76   int N;
 77   cin >> N;
 78   vector<pair<int,int> > towns(N);
 79   for (int i = 0; i < N; i++) {
 80     cin >> towns[i].first >> towns[i].second;
 81   }
 82   int M;
 83   cin >> M;
 84   DisjointSet s(N);
 85   for (int i = 0; i < M; i++) {
 86     int u, v;
 87     cin >> u >> v;
 88     --u;  --v;
 89     s.unite(u, v);
 90   }
 91 
 92   vector<edge> es;
 93   for (int i = 0; i < N; i++) {
 94     for (int j = i+1; j < N; j++) {
 95       if (!s.find(i, j)) {
 96         es.push_back(edge(i, j, dist(towns[i], towns[j])));
 97       }
 98     }
 99   }
100   sort(es.begin(), es.end());
101   const vector<edge> ans = kruskal(es, s);
102   for (vector<edge>::const_iterator it = ans.begin(); it != ans.end(); ++it) {
103     cout << it->u+1 << " " << it->v+1 << endl;
104   }
105   return 0;
106 }
poj/1751.cc