質問編集履歴
2
タイトルの修正。
test
CHANGED
|
@@ -1 +1 @@
|
|
|
1
|
-
Hopcroft-karpの
|
|
1
|
+
Hopcroft-karpの幅優先探索がわからない
|
test
CHANGED
|
File without changes
|
1
出典の明記、問題の概要を加筆・修正させていただきました。再度、よろしくお願いいたします。
test
CHANGED
|
@@ -1 +1 @@
|
|
|
1
|
-
Hopcr
|
|
1
|
+
Hopcroft-karpの深さ優先探索がわからない
|
test
CHANGED
|
@@ -1,12 +1,13 @@
|
|
|
1
1
|
### 実現したいこと
|
|
2
2
|
この問題のプログラムの34行目から始まる深さ優先探索のやっていることの見当がつかず、ヘルプをいただきたいです。
|
|
3
|
-
|
|
3
|
+
[参照サイト](https://drken1215.hatenablog.com/entry/2019/06/17/221400)
|
|
4
|
+
広告を打つ位置を探索で求める問題です。
|
|
4
5
|
|
|
5
6
|
### 発生している問題・分からないこと
|
|
6
7
|
現状の状況を整理です。
|
|
7
8
|
- 全ての頂点を探索して、「left」「right」を割り振り、両方ある頂点ではその「left」「right」で重さ1の辺を張ることまでは理解済み
|
|
8
|
-
- その後、この辺分だけ
|
|
9
|
+
- その後、この辺分だけ幅優先をし最大マッチング数を求めて頂点数から引くことで答えが求まるのも納得済み
|
|
9
|
-
- **この
|
|
10
|
+
- **この幅優先の部分の探索方法がわからないです**
|
|
10
11
|
|
|
11
12
|
|
|
12
13
|
|