Edmonds–Karp (Max Flow) | Алгоритмын сан

Сүлжээгээр нэг node-оос нөгөө рүү хамгийн их урсгал явуулах арга: BFS-ээр path хайж дүүргэнэ.

Advanced & LegendO(n · m²)O(n²)

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

4 node, хоолой нь 1 2 3, 1 3 2, 2 3 1, 2 4 2, 3 4 3. Node 1-ээс 4 хүртэл хамгийн ихдээ хэр их ус урсах вэ?

BFS эхлээд 1 → 2 → 4 path-аар 2, дараа нь 1 → 3 → 4 path-аар 2, сүүлд нь 1 → 2 → 3 → 4 path-аар 1 урсгана. Хариу 5. Node 1-ээс гарах хоолойн нийт багтаамж ч 3 + 2 = 5.

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

Энгийн арга бол сул зайтай аль нэг path-ыг олоод дүүргэх, дахин олох. Гэхдээ эхний сонголт буруу байвал гацна: урсгасан ус өөр, илүү сайн path-ыг хааж болно.

Гол санаа: ус урсгах бүрт эсрэг чиглэлд "буцаах эрх" нэмнэ (cap[v][u] += f). Дараа нь өөр path энэ эрхийг ашиглаж, өмнөх усыг өөр тийш шилжүүлж чадна. Edmonds–Karp path-ыг BFS-ээр хайдаг тул хамгийн цөөн edge-тэй path олддог. Энэ нь давталтын тоог хязгаарладаг.

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

s, t: Ус гарах node (source, энд 1) ба ус очих node (sink, энд n).
cap[u][v]: u → v чиглэлд үлдсэн сул зай (residual capacity). Ус урсгах тусам багасна.
par[v]: BFS-ийн үед v-д аль node-оос ирсэн. Path-ыг t-гээс s хүртэл ухарч сэргээхэд хэрэглэнэ.
f: Олдсон path-ын хамгийн бага сул зай. Энэ path-аар яг f ус урсгана.
min cut: Тасалбал s, t хоёр салах edge-үүдийн хамгийн бага нийт багтаамж. Max Flow-тэй тэнцүү.

flow = 0

хоосон

үлдсэн багтаамж (cap)

1→2: 41→3: 32→3: 22→4: 33→5: 44→5: 24→6: 35→6: 4

Ус node s = 1-ээс node t = 6 хүртэл хоолойгоор урсана. Edge дээр «урсаж буй ус / багтаамж» гэж бичсэн. Нэг дор хамгийн ихдээ хэр их ус урсгаж чадах вэ?

Алхам 1 / 25

Хурд

Space тоглуулах
←→ алхам
−+ хурд

Эх s
Сая хүрсэн node / урсгал нэмэгдсэн path
BFS хүрсэн node
Олдсон path
Ус урсаж буй хоолой
Дүүрсэн хоолой
Төгсгөл t / min cut

Слайд 1 / 7

Усны хоолой

Node s-ээс t руу ус урсгана. Хоолой бүр өөрийн багтаамжтай. Edge дээрх «2/4» нь 4 багтаамжтай хоолойгоор одоо 2 ус урсаж байгааг заана. Хамгийн их урсгалыг олъё.

edmonds-karp.cpp

#include <bits/stdc++.h>

using namespace std;

int n, m, cap[505][505], par[505];

long long flow;

int main() {

cin >> n >> m;

for (int i = 0; i < m; i++) {

int u, v, c;

cin >> u >> v >> c;

cap[u][v] += c;

}

int s = 1, t = n;

while (true) {

memset(par, 0, sizeof par);

par[s] = s;

queue<int> q;

q.push(s);

while (!q.empty() && par[t] == 0) {

int u = q.front();

q.pop();

for (int v = 1; v <= n; v++) {

if (par[v] == 0 && cap[u][v] > 0) {

par[v] = u;

q.push(v);

}

if (par[t] == 0) break;

int f = INT_MAX;

for (int v = t; v != s; v = par[v]) f = min(f, cap[par[v]][v]);

for (int v = t; v != s; v = par[v]) {

cap[par[v]][v] -= f;

cap[v][par[v]] += f;

}

flow += f;

}

cout << flow << '\n';

return 0;

}

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

Хоолой, зам, сувгийн сүлжээгээр хамгийн ихдээ хэр их зүйл дамжуулж болохыг олно. Min cut, хос олох зэрэг олон бодлого урсгал руу шилждэг.

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

1. cap[u][v] бол u → v хоолойд үлдсэн сул зай. Эхэндээ багтаамжтай тэнцүү. 2. s = 1-ээс BFS хийж, сул зайтай хоолойгоор t = n хүрэх хамгийн цөөн edge-тэй path-ыг олно. par[v] нь v-д хаанаас ирснийг санана. 3. Path олдохгүй бол дуусна. 4. Path-ын хамгийн бага сул зай f-ийг олно. 5. Path-ын edge бүрт cap[u][v] -= f, эсрэг чиглэлд нь cap[v][u] += f (дараа нь урсгалыг буцаах боломж). Урсгалд f нэмнэ. Оролт: n m, дараа нь m мөрөнд «u v c» (u → v хоолой, багтаамж c). Эх нь 1, төгсгөл нь n.

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

Max Flow = Min Cut теорем: s-ээс t хүрэх сул зайтай path байхгүй бол одоогийн урсгал хамгийн их. Тэр үед BFS хүрсэн node-ууд ба хүрээгүй node-уудын хоорондох edge-үүд бүгд дүүрсэн, тэдгээрийн багтаамжийн нийлбэр урсгалтай яг тэнцүү. Эсрэг чиглэлийн cap нь өмнөх буруу сонголтыг засах боломж өгдөг тул хариу үргэлж зөв.

BFS хамгийн богино path олдог тул нийт O(n · m) давталт, давталт бүр O(m). Нийт O(n · m²). Энэ код cap-ыг матрицаар хадгалдаг тул n хэдэн зуу хүртэл тохиромжтой.

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

Эсрэг чиглэлийн cap[v][par[v]] += f-ийг мартах. Тэгвэл эхний буруу сонголтыг засаж чадахгүй, хариу бага гарна.
DFS-ээр path хайх. Хариу зөв ч багтаамж том үед маш олон давталт хийж удааширна. BFS ашигла.
Нэг хоолой хоёр удаа өгөгдвөл cap[u][v] = c гэж дарж бичих. Код += хэрэглэдэг.
flow-г int-ээр хадгалах. Олон том багтаамжийн нийлбэр хэтэрч болно, код long long ашигладаг.

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

s-ээс t хүрэх path байхгүй: эхний BFS шууд зогсоно, хариу 0.
Нэг шууд хоолой 1 → n: хариу нь түүний багтаамж.
Эсрэг урсгал хэрэгтэй graph (animation-ы "Эсрэг урсгал" жишээ): сүүлийн path урсгалыг 4 → 2 чиглэлд буцааж, хариу 5 болно.

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

4 node, хоолой нь 1 2 5, 3 4 5. Хариу хэд вэ?
Хариу харах
0. Node 1-ээс 4 хүрэх path алга.
Жижиг жишээнд (1 2 3, 1 3 2, 2 3 1, 2 4 2, 3 4 3) хэдэн удаа ус урсгах вэ?
Хариу харах
3 удаа: 2, 2, 1. Дөрөв дэх BFS t-д хүрэхгүй.

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

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

1.Бүх хоолойн багтаамж 1: 1 2, 1 3, 2 3, 2 4, 3 4. Хамгийн их урсгал хэд вэ?
Hint харах
Node 1-ээс хэдэн хоолой гарч байна вэ?
Хариу ба тайлбар
2. Node 1-ээс гарах хоёр хоолой дүүрнэ: 1 → 2 → 4, 1 → 3 → 4.
2.Хариуны дараа min cut-ын edge-үүдийг хэвлэдэг болго.
Hint харах
Сүүлийн BFS-ийн дараа par[v] != 0 байх node-ууд s талд байна.
Хариу ба тайлбар
Сүүлийн BFS-ээр хүрсэн node-уудыг S гэе. Анхны edge u → v бүрийн хувьд u нь S-д, v нь S-д биш бол тэр edge min cut-д орно.
3.Kuhn-ий бодлогыг (хүүхэд ба бэлэг) Max Flow-оор шийд.
Hint харах
Шинэ s, t node нэмж, бүх хоолойн багтаамжийг 1 болго.
Хариу ба тайлбар
s-ээс зүүн талын node бүр рүү, зүүн node-оос дуртай баруун node руу, баруун node бүрээс t руу 1 багтаамжтай хоолой тавина. Max Flow нь хамгийн олон хос.

Жишээ

Оролт