POJ 1826 - The Best Farm

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

概要

\(N\) 個の格子点の座標 \((x_i, y_i)\)と、そこに割り当てられた価値 \(v_i\) が与えられる。 上下左右に隣接している格子点は連結した領域としてみなされる。 1つ以上の連結した領域の価値は、その領域の各格子点の価値の和である。 このとき、領域の価値の最大値を答える。

制約

• \(1 \le N \le 2 \cdot 10 ^ 5\)
• \(x_i, y_i\) は 16bit signed integer に収まる
• \(0 \le v_i \le 10 ^ 4\)

解法

マップが広くて二次元配列では持てないので、std::map で持つようにして BFS して数えた。 このとき、座標を std::pair で持つと TLE したので long long な値に適当にエンコードしたり、ちょっと高速化すると通った。 Union-Find で数えるともっと高速に通るらしい。

 1 #include <cstdio>
 2 #include <map>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 
 8 int main()
 9 {
10   static const ll GETA = 40000, T = 100000;
11   int N;
12   while (scanf("%d", &N) != EOF && N != 0) {
13     map<ll, int> m;
14     for (int i = 0; i < N; i++) {
15       int x, y, val;
16       scanf("%d %d %d", &x, &y, &val);
17       m.insert(make_pair((x+GETA)*T + y+GETA, val));
18     }
19 
20     int ans = 0;
21     while (!m.empty()) {
22       map<ll, int>::iterator jt = m.begin();
23       queue<ll> q;
24       int val = jt->second;
25       q.push(jt->first);
26       m.erase(jt);
27       while (!q.empty()) {
28         const ll pos = q.front();
29         q.pop();
30         const int i = pos/T, j = pos%T;
31         for (int d = 0; d < 4; d++) {
32           static const int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};
33           const ll next = (i+di[d])*T + j+dj[d];
34           jt = m.find(next);
35           if (jt != m.end()) {
36             val += jt->second;
37             q.push(jt->first);
38             m.erase(jt);
39           }
40         }
41       }
42       ans = max(ans, val);
43     }
44     printf("%d\n", ans);
45   }
46   return 0;
47 }