POJ 2226 - Muddy Fields

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

概要

\(R \times C\) のグリッドが与えられ、いくつかのマスはぬかるんでいる。 すべてのぬかるんでいるマスを板で覆いたい。 この板は幅は1であるが、長さは好きなだけ長くできる。 板同士が重なっても構わないが、ぬかるんでいないマスを板で覆ってはならない。 このとき、必要な最小の板の枚数を答える。

制約

• \(1 \le R, C \le 50\)

解法

板同士は重なっていいので、ぬかるんでいないマスを覆わない限りできるだけ長く使ったほうがいい。 あるぬかるんでいるマスを最適に覆うには、そのマスからなるべく左側にあるぬかるんでいるマスから行方向に板を置くか、 そのマスからなるべく上側にあるぬかるんでいるますから列方向に板を置くかのいずれかである。 このような関係をエッジで表すと問題は二部グラフの最小頂点被覆問題に帰着でき、つまり二部グラフの最大マッチングを求めればいい。

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 bool bm_augment(const vector<vector<int> >& g, int u, vector<int>& match_to, vector<bool>& visited) // {{{
 6 {
 7   if (u < 0) {
 8     return true;
 9   }
10 
11   for (vector<int>::const_iterator it(g[u].begin()); it != g[u].end(); ++it) {
12     if (!visited[*it]) {
13       visited[*it] = true;
14       if (bm_augment(g, match_to[*it], match_to, visited)) {
15         match_to[u] = *it;
16         match_to[*it] = u;
17         return true;
18       }
19     }
20   }
21   return false;
22 } // }}}
23 
24 // O(V(V+E))
25 int bipartite_matching(const vector<vector<int> >& g)  // {{{
26 {
27   const int N = g.size();
28   vector<int> match_to(N, -1);
29   int match = 0;
30   for (int u = 0; u < N; u++) {
31     vector<bool> visited(N, false);
32     if (bm_augment(g, u, match_to, visited)) {
33       match++;
34     }
35   }
36   return match;
37 } // }}}
38 
39 int main()
40 {
41   int R, C;
42   cin >> R >> C;
43   vector<string> grid(R);
44   for (int i = 0; i < R; i++) {
45     cin >> grid[i];
46   }
47 
48   const int N = R*C;
49   vector<vector<int> > g(2*N);
50   for (int i = 0; i < R; i++) {
51     for (int j = 0; j < C; j++) {
52       if (grid[i][j] == '*') {
53         int k = i;
54         while (k > 0 && grid[k-1][j] == '*') {
55           --k;
56         }
57         int l = j;
58         while (l > 0 && grid[i][l-1] == '*') {
59           --l;
60         }
61         g[k*C+j].push_back(N + i*C+l);
62       }
63     }
64   }
65 
66   cout << bipartite_matching(g) << endl;
67   return 0;
68 }