Meydan okuma 4
- Algoritmalar kursu
- Uzman seviye
- Ders 40/41
- 4 dk
Maksimum akışı yazdırırsın.
Meydan okuma 4 - Maksimum akış
Dördüncü meydan okuma, Ford-Fulkerson maksimum akış algoritmasını yoklar. Artık yollarla akışı artırır ve her yol için darboğaz kadar akış ekler.
count_doublings, kmp_search ve convex_hull fonksiyonları yukarıda hazırdır; sen ford_fulkerson yazacaksın. DFS ile artık yol bul, darboğaz kadar artır.
Bu meydan okuma, birikimli zincirin dördüncü halkasıdır ve ağ akışı konusunu yoklar.
Uygulama ford_fulkerson fonksiyonu
ford_fulkerson(capacity, source, sink) yaz. Maksimum akışı döndür. print(ford_fulkerson([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3), ('a','b',1)], 's', 't')) ile 5 yazdır. Diğer üç fonksiyon yukarıda hazırdır.
Başlangıç kodu
def count_doublings(n):
count = 0
size = 1
last = 0
for i in range(n):
if last == size:
size *= 2
count += 1
last += 1
return count
def kmp_search(text, pattern):
n, m = len(text), len(pattern)
lps = [0] * m
length = 0
i = 1
while i < m:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
elif length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
i = j = 0
while i < n:
if text[i] == pattern[j]:
i += 1
j += 1
if j == m:
return i - j
elif j != 0:
j = lps[j - 1]
else:
i += 1
return -1
def convex_hull(points):
pts = sorted(set(points))
if len(pts) <= 1:
return pts
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
lower = []
for p in pts:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
upper = []
for p in reversed(pts):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
return lower[:-1] + upper[:-1]
def ford_fulkerson(capacity, source, sink):
# Maksimum akışı döndürÖrnek çözüm
def ford_fulkerson(capacity, source, sink):
from collections import defaultdict
graph = defaultdict(dict)
for u, v, c in capacity:
graph[u][v] = graph[u].get(v, 0) + c
graph[v][u] = graph[v].get(u, 0)
max_flow = 0
def dfs(s, t, flow, visited):
if s == t:
return flow
visited.add(s)
for v in graph[s]:
if v not in visited and graph[s][v] > 0:
pushed = dfs(v, t, min(flow, graph[s][v]), visited)
if pushed > 0:
graph[s][v] -= pushed
graph[v][s] = graph[v].get(s, 0) + pushed
return pushed
return 0
while True:
f = dfs(source, sink, float('inf'), set())
if f == 0:
break
max_flow += f
return max_flow
print(ford_fulkerson([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3), ('a','b',1)], 's', 't'))Beklenen çıktı
5
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Maksimum akış neye eşittir?
- En uzun yola
- Toplam kenara
- Kaynak derecesine
- Minimum kesim kapasitesine Doğru cevap
Açıklama: Maksimum akış minimum kesim kapasitesine eşittir.
2 Max-flow kavramları
| Kavram | Anlamı |
|---|---|
artık yol |
Akış artırma |
darboğaz |
Minimum kapasite |
max_flow |
Akış birikimi |
DFS |
Yol bulma |
3 akış birikimi
max_flow += ____max_flow += fAçıklama: Her artık yolun darboğazı f'ye eklenir.