#29. Maximum Flow (Dinic)
Sizga n ta cho'qqidan iborat va m ta yo'nalishli qirralarga ega bo'lgan tarmoq (graf) beriladi. Har bir yo'nalishli qirra o'zidan o'tkaza oladigan maksimal suv (yoki ma'lumot) sig'imiga (capacity) ega. 1-cho'qqi manba (suv chiqadigan joy) va n-cho'qqi qabul qiluvchi hisoblanadi. Sizning vazifangiz 1-cho'qqidan n-cho'qqiga yuborish mumkin bo'lgan jami maksimal oqim (maximum flow) miqdorini topishdir.
Birinchi qatorda n (cho'qqilar) va m (qirralar) soni. Keyingi m ta qatorda uchtadan son: u (qayerdan), v (qayerga) va c (ushbu qirraning sig'imi).
1-cho'qqidan n-cho'qqiga yetib bora oladigan eng maksimal oqim miqdorini chiqaring.
n ≤ 5000
You are given a network (graph) consisting of n vertices and m directed edges. Each directed edge has a maximum capacity it can let through. Vertex 1 is the source and vertex n is the sink. Your task is to find the total maximum flow that can be sent from vertex 1 to vertex n.
The first line contains the numbers n (vertices) and m (edges). The next m lines contain three numbers each: u (from), v (to), and c (the capacity of this edge).
Output the maximum amount of flow that can reach vertex n from vertex 1.
n ≤ 5000
Вам дана сеть (граф), состоящая из n вершин и m ориентированных ребер. Каждое ориентированное ребро имеет максимальную пропускную способность (емкость). Вершина 1 является источником, а вершина n — стоком. Ваша задача — найти общую величину максимального потока, который можно отправить от вершины 1 к вершине n.
В первой строке заданы числа n (вершины) и m (ребра). В следующих m строках заданы по три числа: u (откуда), v (куда) и c (пропускная способность этого ребра).
Выведите максимальную величину потока, которая может достичь вершины n от вершины 1.
n ≤ 5000
Sizga n ta cho'qqidan iborat va m ta yo'nalishli qirralarga ega bo'lgan tarmoq (graf) beriladi. Har bir yo'nalishli qirra o'zidan o'tkaza oladigan maksimal suv (yoki ma'lumot) sig'imiga (capacity) ega. 1-cho'qqi manba (suv chiqadigan joy) va n-cho'qqi qabul qiluvchi hisoblanadi. Sizning vazifangiz 1-cho'qqidan n-cho'qqiga yuborish mumkin bo'lgan jami maksimal oqim (maximum flow) miqdorini topishdir.
Kiruvchi ma'lumotlar
Birinchi qatorda n (cho'qqilar) va m (qirralar) soni. Keyingi m ta qatorda uchtadan son: u (qayerdan), v (qayerga) va c (ushbu qirraning sig'imi).
Chiquvchi ma'lumotlar
1-cho'qqidan n-cho'qqiga yetib bora oladigan eng maksimal oqim miqdorini chiqaring.
Cheklovlar
n ≤ 5000
Misollar
4 5 1 2 10 1 3 5 2 3 15 2 4 5 3 4 10
15