POJ 3020 - Antenna Placement

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

概要

w * h のグリッド上にいくつか interest がある (interest の意味がわからなかった…)． interest のある位置にアンテナを置くと，その interest をカバーすることができる． さらに，アンテナを (c,r) の位置に置いたとすると，(c+1,r), (c,r+1), (c-1,r), (c,r-1) のいずれかの位置の interest もカバーすることができる．

すべての interest をカバーするのに必要な最小のアンテナの数を答える．

制約

• 1 <= h <= 40
• 0 < w <= 10

解法

1つのアンテナに同時にカバーされるペアをなるべく多く作ればいい． 同時にカバーされうる点同士を結ぶと二部グラフになり，点の数 - 最大マッチング が答えになる．

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 bool augument(const vector<vector<int> >& g, int u, vector<int>& match_to, vector<bool>& visited)/*{{{*/
 7 {
 8   if (u < 0) {
 9     return true;
10   }
11 
12   for (vector<int>::const_iterator it(g[u].begin()); it != g[u].end(); ++it) {
13     if (!visited[*it]) {
14       visited[*it] = true;
15       if (augument(g, match_to[*it], match_to, visited)) {
16         match_to[*it] = u;
17         return true;
18       }
19     }
20   }
21   return false;
22 }/*}}}*/
23 
24 void coloring(const vector<vector<int> >& g, int u, vector<int>& color)/*{{{*/
25 {
26   for (vector<int>::const_iterator it = g[u].begin(); it != g[u].end(); ++it) {
27     if (color[*it] == 0) {
28       color[*it] = -color[u];
29       coloring(g, *it, color);
30     }
31   }
32 }/*}}}*/
33 
34 int bipartite_matching(const vector<vector<int> >& g)/*{{{*/
35 {
36   const int N = g.size();
37   vector<int> color(N, 0);
38   for (int u = 0; u < N; u++) {
39     if (color[u] == 0) {
40       color[u] = 1;
41       coloring(g, u, color);
42     }
43   }
44   vector<int> match_to(N, -1);
45   int match = 0;
46   vector<bool> visited(N);
47   for (int u = 0; u < N; u++) {
48     if (color[u] == 1) {
49       fill(visited.begin(), visited.end(), false);
50       if (augument(g, u, match_to, visited)) {
51         match++;
52       }
53     }
54   }
55   return match;
56 }/*}}}*/
57 
58 int main()
59 {
60   int N;
61   cin >> N;
62   while (N-- > 0) {
63     int H, W;
64     cin >> H >> W;
65     vector<string> grid(H);
66     for (int i = 0; i < H; i++) {
67       cin >> grid[i];
68     }
69 
70     vector<vector<int> > g(H*W);
71     int c = 0;
72     for (int i = 0; i < H; i++) {
73       for (int j = 0; j < W; j++) {
74         if (grid[i][j] == '*') {
75           ++c;
76           if (j+1 < W && grid[i][j+1] == '*') {
77             g[i*W+j].push_back(i*W+j+1);
78             g[i*W+j+1].push_back(i*W+j);
79           }
80           if (i+1 < H && grid[i+1][j] == '*') {
81             g[i*W+j].push_back((i+1)*W+j);
82             g[(i+1)*W+j].push_back(i*W+j);
83           }
84         }
85       }
86     }
87 
88     const int m = bipartite_matching(g);
89     cout << c-m << endl;
90   }
91   return 0;
92 }