Хамгийн их урсгал - Диникийн алгоритм¶
Диникийн алгоритм хамгийн их урсгалын бодлогыг $O(V^2E)$-д бодно. Хамгийн их урсгалын бодлогыг Хамгийн их урсгал - Форд-Фалкерсон ба Эдмондс-Карп өгүүлэлд тодорхойлсон. Энэ алгоритмыг Ефим Диниц 1970 онд нээсэн.
Тодорхойлолтууд¶
Сүлжээ $G$-ийн үлдэгдэл сүлжээ $G^R$ гэдэг нь ирмэг $(v, u)\in G$ бүрийн хувьд хоёр ирмэг агуулах сүлжээ юм:
- $c_{vu}^R = c_{vu} - f_{vu}$ багтаамжтай $(v, u)$
- $c_{uv}^R = f_{vu}$ багтаамжтай $(u, v)$
Ямар нэг сүлжээний хаагч урсгал гэдэг нь $s$-ээс $t$ хүрэх зам бүр энэ урсгалаар ханасан дор хаяж нэг ирмэг агуулж байх урсгал юм. Хаагч урсгал заавал максимал байх албагүйг анхаарна уу.
Сүлжээ $G$-ийн давхаргат сүлжээ гэдэг нь дараах байдлаар байгуулсан сүлжээ юм. Эхлээд орой $v$ бүрийн хувьд бид $level[v]$-г буюу зөвхөн эерэг багтаамжтай ирмэгүүдийг ашиглан $s$-ээс энэ орой хүрэх (жингүй) хамгийн богино замыг тооцоолно. Дараа нь бид зөвхөн $level[v] + 1 = level[u]$ байх ирмэг $(v, u)$-г үлдээнэ. Илэрхий байдлаар энэ сүлжээ циклгүй.
Алгоритм¶
Алгоритм хэд хэдэн фазаас тогтоно. Фаз бүрд бид $G$-ийн үлдэгдэл сүлжээний давхаргат сүлжээг байгуулна. Дараа нь бид давхаргат сүлжээнд дурын хаагч урсгалыг олж, түүнийг одоогийн урсгалд нэмнэ.
Зөв байдлын баталгаа¶
Хэрэв алгоритм дуусвал тэр хамгийн их урсгалыг олдгийг харуулъя.
Хэрэв алгоритм дууссан бол тэр давхаргат сүлжээнд хаагч урсгал олж чадаагүй гэсэн үг. Энэ нь давхаргат сүлжээнд $s$-ээс $t$ хүрэх ямар ч зам байхгүй гэсэн үг. Энэ нь үлдэгдэл сүлжээнд $s$-ээс $t$ хүрэх ямар ч зам байхгүй гэсэн үг. Энэ нь урсгал хамгийн их гэсэн үг.
Фазын тоо¶
Алгоритм $V$-ээс бага фазад дуусна. Үүнийг батлахын тулд бид эхлээд хоёр леммыг батлах ёстой.
Лемм 1. $s$-ээс орой бүр хүрэх зай итерац бүрийн дараа буурахгүй, өөрөөр хэлбэл $level_{i+1}[v] \ge level_i[v]$.
Баталгаа. Фаз $i$ ба орой $v$-г тогтооно. $G_{i+1}^R$ дэх $s$-ээс $v$ хүрэх дурын хамгийн богино зам $P$-г авч үзье. $P$-ийн урт нь $level_{i+1}[v]$-тэй тэнцүү. $G_{i+1}^R$ нь зөвхөн $G_i^R$-ийн ирмэгүүд ба $G_i^R$-ийн ирмэгүүдийн буцах ирмэгүүдийг агуулж болохыг анхаар. Хэрэв $P$ нь $G_i^R$-ийн хувьд буцах ирмэггүй бол $P$ нь мөн $G_i^R$ дэх зам тул $level_{i+1}[v] \ge level_i[v]$ болно. Одоо $P$ дор хаяж нэг буцах ирмэгтэй гэж үзье. Ийм эхний ирмэг нь $(u, w)$ байг. Тэгвэл $level_{i+1}[u] \ge level_i[u]$ (эхний тохиолдлоос болж). Ирмэг $(u, w)$ нь $G_i^R$-д харьяалагдахгүй тул ирмэг $(w, u)$ өмнөх итерацад хаагч урсгалаар нөлөөлөгдсөн. Энэ нь $level_i[u] = level_i[w] + 1$ гэсэн үг. Мөн $level_{i+1}[w] = level_{i+1}[u] + 1$. Эдгээр хоёр тэгшитгэл ба $level_{i+1}[u] \ge level_i[u]$-ээс бид $level_{i+1}[w] \ge level_i[w] + 2$-г олж авна. Одоо бид замын үлдсэн хэсэгт ижил санааг ашиглаж болно.
Лемм 2. $level_{i+1}[t] > level_i[t]$
Баталгаа. Өмнөх леммээс $level_{i+1}[t] \ge level_i[t]$. $level_{i+1}[t] = level_i[t]$ гэж үзье. $G_{i+1}^R$ нь зөвхөн $G_i^R$-ийн ирмэгүүд ба $G_i^R$-ийн ирмэгүүдийн буцах ирмэгүүдийг агуулж болохыг анхаар. Энэ нь $G_i^R$-д хаагч урсгалаар хаагдаагүй хамгийн богино зам байна гэсэн үг. Энэ нь зөрчил юм.
Эдгээр хоёр леммээс бид $level[t]$ өсдөг боловч $V - 1$-ээс их байж чадахгүй тул $V$-ээс бага фаз байна гэж дүгнэнэ.
Хаагч урсгал олох¶
Итерац бүрд хаагч урсгалыг олохын тулд бид давхаргат сүлжээнд $s$-ээс $t$ хүртэл DFS-ээр урсгалыг түлхэж болох л бол түлхэхийг зүгээр оролдож болно. Үүнийг илүү хурдан хийхийн тулд бид цаашид түлхэхэд ашиглах боломжгүй болсон ирмэгүүдийг хасах ёстой. Үүний тулд бид орой бүрд ашиглаж болох дараагийн ирмэг рүү заасан заагч хадгалж болно.
Нэг удаагийн DFS ажиллуулалт $O(k+V)$ хугацаа авна, энд $k$ нь энэ ажиллуулалт дахь заагчийн ахилтын тоо юм. Бүх ажиллуулалтын дүнгээр заагчийн ахилтын тоо $E$-ээс хэтэрч чадахгүй. Нөгөө талаас ажиллуулалт бүр дор хаяж нэг ирмэгийг ханадаг тул ажиллуулалтын нийт тоо $E$-ээс хэтрэхгүй. Ингэснээр хаагч урсгал олох нийт ажиллах хугацаа $O(VE)$ болно.
Complexity¶
$V$-ээс бага фаз байгаа тул нийт complexity нь $O(V^2E)$ болно.
Нэгж сүлжээ¶
Нэгж сүлжээ гэдэг нь $s$ ба $t$-ээс бусад дурын оройн хувьд орох эсвэл гарах ирмэг нь цорын ганц бөгөөд нэгж багтаамжтай байх сүлжээ юм. Энэ нь яг л бидний урсгал ашиглан хамгийн их тааруулалтын бодлогыг бодохын тулд байгуулдаг сүлжээний тохиолдол юм.
Нэгж сүлжээн дээр Диникийн алгоритм $O(E\sqrt{V})$-д ажиллана. Үүнийг батлая.
Эхлээд ирмэг бүрийг хамгийн ихдээ нэг удаа авч үзэх тул одоо фаз бүр $O(E)$-д ажиллана.
Хоёрдугаарт аль хэдийн $\sqrt{V}$ фаз болсон гэж үзье. Тэгвэл $\le\sqrt{V}$ урттай бүх нэмэгдүүлэх зам олдсон байна. $f$ нь одоогийн урсгал, $f'$ нь хамгийн их урсгал байг. Тэдгээрийн ялгавар $f' - f$-г авч үзье. Энэ нь $G^R$ дэх $|f'| - |f|$ утгатай урсгал бөгөөд ирмэг бүр дээр $0$ эсвэл $1$ байна. Үүнийг $s$-ээс $t$ хүрэх $|f'| - |f|$ зам ба магадгүй циклүүдэд задалж болно. Сүлжээ нэгж тул тэдгээр нь нийтлэг оройтой байж чадахгүй, тиймээс оройн нийт тоо $\ge (|f'| - |f|)\sqrt{V}$ боловч мөн $\le V$ тул дахин $\sqrt{V}$ итерацын дараа бид хамгийн их урсгалыг гарцаагүй олно.
Нэгж багтаамжтай сүлжээ¶
Бүх ирмэг нэгж багтаамжтай, гэвч орох ба гарах ирмэгийн тоо хязгааргүй илүү ерөнхий тохиолдолд замууд нийтлэг оройтой байхын оронд нийтлэг ирмэгтэй байж чадахгүй. Ижил аргаар энэ нь итерацын тоонд $\sqrt E$ хязгаарыг батлах боломж олгодог тул ийм сүлжээн дээрх Диникийн алгоритмын ажиллах хугацаа хамгийн ихдээ $O(E \sqrt E)$ болно.
Эцэст нь нэгж багтаамжтай сүлжээн дэх фазын тоо $O(V^{2/3})$-ээс хэтрэхгүйг батлах боломжтой бөгөөд энэ нь ялангуяа их тооны ирмэгтэй сүлжээнүүдэд $O(EV^{2/3})$ гэсэн өөр үнэлгээг өгдөг.
Implementation¶
struct FlowEdge {
int v, u;
long long cap, flow = 0;
FlowEdge(int v, int u, long long cap) : v(v), u(u), cap(cap) {}
};
struct Dinic {
const long long flow_inf = 1e18;
vector<FlowEdge> edges;
vector<vector<int>> adj;
int n, m = 0;
int s, t;
vector<int> level, ptr;
queue<int> q;
Dinic(int n, int s, int t) : n(n), s(s), t(t) {
adj.resize(n);
level.resize(n);
ptr.resize(n);
}
void add_edge(int v, int u, long long cap) {
edges.emplace_back(v, u, cap);
edges.emplace_back(u, v, 0);
adj[v].push_back(m);
adj[u].push_back(m + 1);
m += 2;
}
bool bfs() {
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : adj[v]) {
if (edges[id].cap == edges[id].flow)
continue;
if (level[edges[id].u] != -1)
continue;
level[edges[id].u] = level[v] + 1;
q.push(edges[id].u);
}
}
return level[t] != -1;
}
long long dfs(int v, long long pushed) {
if (pushed == 0)
return 0;
if (v == t)
return pushed;
for (int& cid = ptr[v]; cid < (int)adj[v].size(); cid++) {
int id = adj[v][cid];
int u = edges[id].u;
if (level[v] + 1 != level[u])
continue;
long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));
if (tr == 0)
continue;
edges[id].flow += tr;
edges[id ^ 1].flow -= tr;
return tr;
}
return 0;
}
long long flow() {
long long f = 0;
while (true) {
fill(level.begin(), level.end(), -1);
level[s] = 0;
q.push(s);
if (!bfs())
break;
fill(ptr.begin(), ptr.end(), 0);
while (long long pushed = dfs(s, flow_inf)) {
f += pushed;
}
}
return f;
}
};