POJ 2420 - A Star not a Tree?

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

概要

N 個のコンピュータがあって，それぞれを1つのハブにケーブルで繋ぎたい． N 個のコンピュータの座標が与えられたとき，ハブをうまく設置して N 本のケーブルの長さの和を最小化する問題．

和は最も近い整数に丸めて答える．

制約

• 0 < N <= 100
• 座標の値は区間 [0, 10000]

解法

山登り法で解いた．1000回もループさせる必要は無いかも．

 1 #include <iostream>
 2 #include <vector>
 3 #include <complex>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 typedef complex<double> P;
 8 
 9 double total_dist(const vector<P>& ps, const P& p)
10 {
11   double s = 0.0;
12   for (vector<P>::const_iterator it = ps.begin(); it != ps.end(); ++it) {
13     s += abs(*it - p);
14   }
15   return s;
16 }
17 
18 int main()
19 {
20   int N;
21   cin >> N;
22   vector<P> ps(N);
23   for (int i = 0; i < N; i++) {
24     cin >> ps[i].real() >> ps[i].imag();
25   }
26   double step = 10000.0;
27   P p = ps[0];
28   double m = total_dist(ps, p);
29   for (int i = 0; i < 1000; i++) {
30     static const int di[] = {-1, 1, 0, 0};
31     static const int dj[] = {0, 0, -1, 1};
32     P next[4];
33     double ls[4];
34     for (int d = 0; d < 4; d++) {
35       next[d] = p + P(di[d]*step, dj[d]*step);
36       ls[d] = total_dist(ps, next[d]);
37     }
38     const int j = distance(ls, min_element(ls, ls+4));
39     m = ls[j];
40     p = next[j];
41     step /= 2.0;
42   }
43   cout << lround(m) << endl;
44   return 0;
45 }