実現したいこと
この問題のプログラムの34行目から始まる深さ優先探索のやっていることの見当がつかず、ヘルプをいただきたいです。
参照サイト
広告を打つ位置を探索で求める問題です。
発生している問題・分からないこと
現状の状況を整理です。
- 全ての頂点を探索して、「left」「right」を割り振り、両方ある頂点ではその「left」「right」で重さ1の辺を張ることまでは理解済み
- その後、この辺分だけ幅優先をし最大マッチング数を求めて頂点数から引くことで答えが求まるのも納得済み
- この幅優先の部分の探索方法がわからないです
該当のソースコード
C++
1#include <iostream> 2#include <vector> 3#include <queue> 4#include <algorithm> 5using namespace std; 6 7 8struct HopcroftKarp { 9 int sizeL, sizeR; 10 vector<vector<int> > list; // left to right 11 12 // result 13 vector<bool> seen, matched; 14 vector<int> level, matching; 15 16 // base 17 HopcroftKarp(int l, int r) : sizeL(l), sizeR(r), list(l, vector<int>()) { } 18 inline vector<int>& operator [] (int i) { return list[i]; } 19 inline void addedge(int from, int to) { list[from].push_back(to); } 20 inline friend ostream& operator << (ostream& s, const HopcroftKarp& G) { 21 s << endl; 22 for (int i = 0; i < G.list.size(); ++i) { 23 s << i << " : "; 24 for (int j = 0; j < G.list[i].size(); ++j) { 25 s << G.list[i][j]; 26 if (j + 1 != G.list[i].size()) s << ", "; 27 } 28 s << endl; 29 } 30 return s; 31 } 32 33 // methods 34 void hobfs() { 35 queue<int> que; 36 for (int left = 0; left < sizeL; ++left) { 37 level[left] = -1; 38 if (!matched[left]) { 39 que.push(left); 40 level[left] = 0; 41 } 42 } 43 level[sizeL] = sizeL; 44 while (!que.empty()) { 45 int left = que.front(); 46 que.pop(); 47 for (int i = 0; i < list[left].size(); ++i) { 48 int right = list[left][i]; 49 int next = matching[right]; 50 if (level[next] == -1) { 51 level[next] = level[left] + 1; 52 que.push(next); 53 } 54 } 55 } 56 } 57 bool hodfs(int left) { 58 if (left == sizeL) return true; 59 if (seen[left]) return false; 60 seen[left] = true; 61 for (int i = 0; i < list[left].size(); ++i) { 62 int right = list[left][i]; 63 int next = matching[right]; 64 if (level[next] > level[left] && hodfs(next)) { 65 matching[right] = left; 66 return true; 67 } 68 } 69 return false; 70 } 71 int solve() { 72 seen.assign(sizeL, false); 73 matched.assign(sizeL, false); 74 level.assign(sizeL+1, -1); 75 matching.assign(sizeR, sizeL); 76 int res = 0; 77 while (true) { 78 hobfs(); 79 seen.assign(sizeL, false); 80 bool finished = true; 81 for (int left = 0; left < sizeL; ++left) { 82 if (!matched[left] && hodfs(left)) { 83 matched[left] = true; 84 ++res; 85 finished = false; 86 } 87 } 88 if (finished) break; 89 } 90 return res; 91 } 92}; 93 94const int dx[4] = {1, 0, -1, 0}; 95const int dy[4] = {0, 1, 0, -1}; 96 97int main() { 98 int R, C; cin >> R >> C; 99 vector<string> fi(R); 100 for (int i = 0; i < R; ++i) cin >> fi[i]; 101 102 HopcroftKarp hk(R*C, R*C); 103 int V = R*C; 104 for (int i = 0; i < R; ++i) { 105 for (int j = 0; j < C; ++j) { 106 int left = i * C + j; 107 cout << "left=" << left << endl; 108 cout << "i=" << i << endl; 109 cout << "j=" << j << endl; 110 if (fi[i][j] == '*') { 111 --V; 112 continue; 113 } 114 if ( (i + j) % 2 == 1 ) continue; 115 for (int dir = 0; dir < 4; ++dir) { 116 int ni = i + dx[dir], nj = j + dy[dir]; 117 cout << "ni=" << ni << endl; 118 cout << "nj=" << nj << endl; 119 if (ni < 0 || ni >= R || nj < 0 || nj >= C) continue; 120 cout << "fi[ni][nj]=" << fi[ni][nj] << endl; 121 if (fi[ni][nj] == '*') continue; 122 int right = ni * C + nj; 123 cout << "right=" << right << endl; 124 hk.addedge(left, right); 125 } 126 } 127 } 128 auto res = hk.solve(); 129 cout << V - res << endl; 130}
試したこと・調べたこと
- teratailやGoogle等で検索した
- ソースコードを自分なりに変更した
- 知人に聞いた
- その他
上記の詳細・結果
検索➔Hopcraftkarpの説明は出てくるも探索については説明なし
改変➔SIZELやSIZERを出力するもよくわからず。
補足
- おそらく、leftからrightへの「s-tパス」みたいなのを44行目以降あたりからやっているのかなとは思いつつ、「う~ん」という感じです。
- 𠮟咤激励含めてコメント・ご回答いただけると幸いです。
他人の書いたソースコード (あなたが後から手を加えた場合も含む) を引用する場合、最低限、そのコードの出所を明記してください。出所とは、ウェブサイトならURL、書籍なら著者名、標題、出版社、該当のページ番号、といったことです。
出所の明記などがない場合、著作権侵害等の権利侵害となることがあります。今後質問する際も気をつけてください。
> 検索➔Hopcraftkarpの説明は出てくるも探索については説明なし
そうなんですか? 「Hopcroft-Karpの深さ優先探索」でウェブ検索すると、この探索アルゴリズムの解説はいろいろみつかるようですけど。
ご回答ありがとうございます。
次回から明記の件、しっかりとしていきます。ありがとうございます。
質問文は編集できます。今回から明記してほしいです。
それと、
・「Hopcroft-Karp」の綴りがまちがっています。質問を見落とされるかもしれませんし、質問者さんの真剣さも疑われかねません。
・34行めからのメソッドは「BFS」という名前なのですが、深さ優先探索なのでしょうか。元々コードを書いた方もそうしていたのか、質問者さんが書き換えたりした結果こうなっているのか、どちらでしょうか。
アルゴリズム名称の誤記を修正されたようですが、Karpは人名ですから最初が大文字です。
