Хоёр талт graph-т хамгийн олон хос үүсгэх арга: хос хайж, хэрэгтэй бол өмнөх хосуудыг сэлгэнэ.

Advanced & LegendХугацаа: O(n · m)Санах ой: O(n + m)

Эхлээд жижиг бодлого

L1 нь R1, R2-т дуртай, L2 нь зөвхөн R1-д дуртай. Эхлээд L1 R1-ийг авна. Дараа нь L2 R1-ийг хүснэ.

L1-ээс "өөр бэлэг авч болох уу?" гэж асуухад L1 R2 руу шилжинэ. R1 суллагдаж L2 авна. Хариу 2 хос: L2–R1, L1–R2.

Энгийн аргаас санаа руу

Энгийн арга бол edge-үүдийн бүх дэд олонлогийг шалгах. 20 edge бол сая гаруй хувилбар.

Kuhn-ийн санаа: зүүн талын node бүрт хос хайна. Хүссэн баруун node сул бол шууд авна. Эзэнтэй бол эзнээс нь өөр хос олж чадах эсэхийг recursion-оор асууна. Ингэж олдсон гинжийг augmenting path гэнэ: түүний дагуу хосуудыг сэлгэхэд хосын тоо яг 1-ээр нэмэгддэг.

Нэр томьёо ба тэмдэглэгээ

bipartite graph
Node-ууд зүүн (L) ба баруун (R) гэж хоёр талд хуваагдсан, edge зөвхөн хоёр талын хооронд байх graph.
matching
Нэг ч node давхардахгүй edge-үүдийн олонлог. Энд хос гэж нэрлэнэ.
mt[v]
Баруун талын v-тэй хос болсон зүүн node. 0 бол сул.
used[u]
Энэ ээлжинд зүүн node u-г аль хэдийн асуусан эсэх.
augmenting path
Сул зүүн node-оос сул баруун node хүрэх, хос биш ба хос edge ээлжилсэн path.
L1L2L3L4R1R2R3R4
ans = 0
mt — бэлэг хэнд очсон
R1: —R2: —R3: —R4: —
used — энэ ээлжинд асуусан
хоосон

Зүүн талд 4 хүүхэд, баруун талд 4 бэлэг байна. Edge нь хүүхэд тэр бэлэгт дуртайг заана. Хүүхэд бүр нэг л бэлэг авна. Аль болох олон хүүхдэд бэлэг өгье!

Алхам 1 / 37
Хурд
  • Одоо шалгаж буй
  • Сая үүссэн хос
  • Хос болсон node ба edge
  • Энэ ээлжинд асуусан
Слайд 1 / 6

Хамгийн олон хос

Зүүн талд хүүхдүүд, баруун талд бэлгүүд байна. Edge нь «энэ хүүхэд энэ бэлэгт дуртай» гэсэн үг. Хүүхэд бүр нэг л бэлэг авна. Аль болох олон хүүхдийг баярлуулъя!

kuhn-matching.cpp
#include <bits/stdc++.h>
using namespace std;
int n1, n2, m, ans, mt[505];
bool used[505];
vector<int> g[505];
bool kuhn(int u) {
if (used[u]) return false;
used[u] = true;
for (int v : g[u]) {
if (mt[v] == 0 || kuhn(mt[v])) {
mt[v] = u;
return true;
}
}
return false;
}
int main() {
cin >> n1 >> n2 >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
}
for (int u = 1; u <= n1; u++) {
memset(used, 0, sizeof used);
if (kuhn(u)) {
ans++;
}
}
cout << ans << '\n';
for (int v = 1; v <= n2; v++) if (mt[v] != 0) cout << mt[v] << ' ' << v << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Хүүхэд ба бэлэг, ажилчин ба ажил гэх мэт хоёр бүлгийг хамгийн олон хосоор холбоно. Олимпиадад «хүснэгтэд домино тавих», «хамгийн бага бүрхэц» зэрэг бодлого үүн рүү шилждэг.

Яаж ажилладаг вэ?

1. Зүүн талын node u бүрийн хувьд used array-г цэвэрлээд kuhn(u) дуудна. 2. kuhn(u) дуудлага: u-гийн хөрш v бүрийг шалгана. 3. v сул (mt[v] = 0) эсвэл одоогийн эзэн нь өөр хос олж чадвал (kuhn(mt[v]) нь true буцаавал) mt[v] = u болгоод true буцаана. 4. Нэг ээлжинд node бүрээс нэг л удаа асууна (used). Тэгэхгүй бол төгсгөлгүй давтана. 5. kuhn(u) true буцаах бүрт хосын тоо 1-ээр нэмэгдэнэ. Оролт: n1 n2 m, дараа нь m мөрөнд «a b» (зүүн талын a, баруун талын b). Гаралт: хосын тоо, дараа нь хос бүр.

Яагаад зөв, хэр хурдан бэ?

Berge-ийн теорем: augmenting path байхгүй бол хос хамгийн их. kuhn(u) нь u дээрээс эхэлсэн augmenting path-ыг DFS-ээр хайдаг. used нь нэг ээлжинд зүүн node бүрийг нэг л удаа оруулна, тэгэхгүй бол хоёр хүүхэд бие биенээсээ асуусаар хэзээ ч дуусахгүй. Зүүн node бүрийн ээлжинд олдсон path хосыг 1-ээр нэмдэг, олдохгүй бол дараа нь ч тэр node-д хос олдохгүй.

Зүүн node бүрт нэг DFS, DFS бүр O(n + m). Нийт O(n · m). n = 500, m = 10 000 бол 5 сая орчим алхам.

Түгээмэл алдаа

  • Ээлж бүрийн өмнө used-ыг цэвэрлэхгүй байх. Код memset(used, 0, sizeof used) хийдэг.
  • used-ыг баруун талын node дээр тавих. Энэ кодод used нь зүүн талын node-д хамаарна.
  • Хариу болгож mt-д бичигдсэн бүх утгыг хэвлэх. Сул баруун node-д 0 байгаа тул mt[v] != 0-ыг шалга.

Хязгаарын тохиолдол

  • Edge байхгүй: хариу 0.
  • Бүгд нэг л баруун node-д дуртай: хариу 1.
  • Зүүн тал баруунаас олон: хариу хамгийн ихдээ баруун талын node-ын тоо.

Өөрийгөө шалга

  1. L1, L2, L3 бүгд зөвхөн R1-д дуртай. Хамгийн олон хос хэд вэ?

    Хариу харах

    1. R1 нэг л хүүхдэд очно.

  2. Animation-ы "Бүгд хүрэлцэхгүй" жишээнд (1 1, 2 1, 3 1, 3 2, 4 2, 4 3) хариу хэд вэ?

    Хариу харах

    3. L1–R1, L3–R2, L4–R3. L2 нь зөвхөн R1-д дуртай тул хос олдохгүй.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.3 хүүхэд, 3 бэлэг: 1 1, 1 2, 2 1, 3 2, 3 3. Код ямар хосуудыг хэвлэх вэ?

    Hint харах

    L1 R1-ийг авна. L2 R1-ийг хүсэхэд юу болох вэ?

    Хариу ба тайлбар

    3 хос: L2–R1, L1–R2, L3–R3. Код баруун талын дарааллаар 2 1, 1 2, 3 3 гэж хэвлэнэ.

  2. 2.n × m хүснэгтийн зарим нүд хаалттай. Нээлттэй нүдэнд 1 × 2 домино хамгийн ихдээ хэдийг тавих вэ?

    Hint харах

    Нүдийг шатрын хөлөг шиг хар, цагаан гэж будна. Домино бүр нэг хар, нэг цагаан нүд эзэлнэ.

    Хариу ба тайлбар

    Хар нүдийг зүүн тал, цагааныг баруун тал болгоно. Хажуу нээлттэй нүднүүдийг edge-ээр холбоод Kuhn ажиллуулна. Хосын тоо хариу.

  3. 3.Хамгийн бага vertex cover: edge бүрийн ядаж нэг үзүүрт тэмдэг тавих хамгийн цөөн node. Bipartite graph-т хэд вэ?

    Hint харах

    Kőnig-ийн теоремыг хай.

    Хариу ба тайлбар

    Bipartite graph-т хамгийн бага vertex cover нь хамгийн их matching-тай тэнцүү. Kuhn-ий хариу шууд хариу болно.

Жишээ

Оролт

4 4 7
1 1
1 2
2 1
3 2
3 3
4 3
4 4

Гаралт

4
2 1
1 2
3 3
4 4