POJ 3099 - Go Go Gorelians

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

概要

N 個の惑星を次々と征服してワープリンクによるネットワークを作っている．

新たに惑星を征服したとき，今まで征服した惑星の中で最もその惑星に近い惑星との間にのみワープリンクを作る． ただし，距離が等しい惑星が複数存在する場合は先に征服した惑星が選ばれる．

このネットワークにおける optimal location を答える．optimal location は1つか2つ存在する．

optimal location とは，他の惑星からその惑星へ行くのに必要なワープ回数の最大値が最小になるような惑星である．

制約

解法

このネットワークは木になっているので，2回の BFS で最遠点対を求めて，それらを結ぶ経路の真ん中のノードを答えればよい．

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 static const int INF = 10000000;
 7 
 8 struct planet { int id, x, y, z; };
 9 
10 int inline sqr(int x) { return x * x; }
11 
12 int bfs(const vector<vector<int> >& g, int start, vector<int>& prev)
13 {
14   const int N = g.size();
15   prev.assign(N, -1);
16   queue<int> q;
17   q.push(start);
18   vector<int> dist(N, INF);
19   dist[start] = 0;
20   int maxd = 0;
21   int idx = 0;
22   while (!q.empty()) {
23     const int n = q.front();
24     q.pop();
25     const int d = dist[n];
26     if (maxd < d) {
27       maxd = dist[n];
28       idx = n;
29     }
30     for (vector<int>::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
31       if (d+1 < dist[*it]) {
32         prev[*it] = n;
33         dist[*it] = d+1;
34         q.push(*it);
35       }
36     }
37   }
38   return idx;
39 }
40 
41 int main()
42 {
43   int N;
44   while (cin >> N && N != 0) {
45     vector<planet> ps;
46     vector<vector<int> > g(N);
47     for (int i = 0; i < N; i++) {
48       planet p;
49       cin >> p.id >> p.x >> p.y >> p.z;
50       ps.push_back(p);
51       int m = INF;
52       int idx = -1;
53       for (int j = 0; j < i; j++) {
54         const int d = sqr(ps[j].x - p.x) + sqr(ps[j].y - p.y) + sqr(ps[j].z - p.z);
55         if (d < m) {
56           m = d;
57           idx = j;
58         }
59       }
60       if (idx != -1) {
61         g[i].push_back(idx);
62         g[idx].push_back(i);
63       }
64     }
65 
66     vector<int> prev;
67     const int u = bfs(g, 0, prev);
68     const int v = bfs(g, u, prev);
69     vector<int> path;
70     for (int x = v; prev[x] != -1; x = prev[x]) {
71       path.push_back(x);
72     }
73     path.push_back(u);
74     const int M = path.size();
75     if (M % 2 == 0) {
76       int a = ps[path[M/2-1]].id;
77       int b = ps[path[M/2]].id;
78       if (a > b) {
79         swap(a, b);
80       }
81       cout << a << ' ' << b << endl;
82     } else {
83       cout << ps[path[M/2]].id << endl;
84     }
85   }
86   return 0;
87 }
poj/3099.cc