EDYCJA: odpowiedź jest ZŁA. Przyjąłem (głupie) domniemane założenie, że kiedy przepływ ścieżki rozpoczyna się w czasie s, a kończy w czasie ti przechodzi przez krawędź e, blokuje krawędź e na ten czas. To jednak nie jest prawda. Widzieć *.
Uwaga: Być może takie podejście jest niepotrzebnie skomplikowane lub nieprawidłowe. Chociaż próbowałem to zweryfikować i dokładnie zanotować - nie spędziłem nad tym dużo czasu.
Zakładając, że „gromadzenie zapasów” jest niedopuszczalne, np. Przepływ musi zostać niezwłocznie przekazany. Niech oznacza liczbę krawędzi, a N długość wejściową. Nie określiłem czasu ciągłego ani dyskretnego, ponieważ nie wziąłem go pod uwagę. Powinien działać dla dyskretnego myślenia, dla ciągłości jestem pewien, że jestem pewien.mN
Następnie możemy opisać to rozwiązanie jako zestaw „ścieżek przepływów” od źródła do ujścia. Ścieżka przepływu jest poczwórna która składa się z następujących elementów: Prosta ścieżka P od źródła do ujścia; Czas ścieżki przepływu począwszy s ; Ilość przepływu przez ścieżkę a ; Przepustowość r .(P,s,a,r)Psar
Pozwól, że rozwiązaniem będzie zbiór przepływów ścieżkowych. Możemy zweryfikować, czy rozwiązanie podane przez te ścieżki przepływu jest poprawne w wielomianie czasowym w | F | i N :F|F|N
- Dla każdego zbocza momentu t dodaj sumę przepustowości wszystkich przepływów ścieżki przechodzących przez e w czasie t . Każdy przepływ ścieżki ma czas rozpoczęcia i zakończenia, dlatego musimy jedynie wziąć pod uwagę momenty, w których przepływ ścieżki zaczyna się lub kończy (między tymi momentami nic się nie zmienia w odniesieniu do przepływów ścieżki, które przekraczają krawędź e .etete
- Dla każdej ścieżki przepływowy możemy zweryfikować, czy wszystkim jest to strumień dotrze do zlewu przed czasem .T
- Dla każdej krawędzi możemy zweryfikować, czy przepływ ścieżki przechodzi po jej zniszczeniu, czy nie.
- Dolną granicę przepływu możemy po prostu sprawdzić, sumując wielkości przepływu ścieżek przepływu.B
Teraz „tylko” trzeba pokazać, że liczba path-płynie jest wielomian w .N
Dla danego rozwiązania możemy określić czas, w którym pewien przepływ przekroczył krawędź i kiedy krawędź została zniszczona. Przekształć to w problem z równoważnym rozwiązaniem: istnieją twarde granice na każdej krawędzi, kiedy można jej użyć, a kiedy nie - czas rozpoczęcia i zakończenia. Niech oznacza zbiór wszystkich tych czasów.{t1,...,tk}
Zastanów się nad jakimś niekompaktowym rozwiązaniem i (początkowo) pustym zestawem ścieżek przepływów. Chodzi o to, że iteracyjnie znajdujemy ścieżkę przepływu w nie kompaktowym rozwiązaniu, usuwamy ją i przechowujemy w naszym zestawie ścieżek przepływu.
Znaleźć ścieżki przepływów to początek i koniec od i t j , ı < j , ale nie kończy pomiędzy każdym t p i t q takie, że [ T P , T Q ] ⊆ [ t i , t j ] . Niech K I , J oznacza zbiór ścieżki przepływów między t J i t j o właściwościach opisanych powyżej.titji<jtptq[tp,tq]⊆[ti,tj]Fi,jtjtj
Załóżmy, że już usunęliśmy wszystkie przepływy ścieżek dla wszystkich mniejszych przedziałów niż . Chciwie znajduj przepływy ścieżek, które zaczynają się i kończą w [ t i , t j ] . Kiedy go znajdziemy, usuń ten przepływ z rozwiązania i odpowiednio dostosuj przepustowości wierzchołków oraz ilość przepływu wysyłanego ze źródła do tonącego. Dla tego przepływu ścieżki maksymalizujemy przepustowość. Oznacza to, że dla co najmniej jednej krawędzi osiągnęliśmy maksymalną przepustowość lub po usunięciu tego przepływu ścieżki nie ma już przepływu przez tę krawędź. Należy zauważyć, że dotyczy to okresu [ t i + 1 , t j[i,j][ti,tj]. W obu przypadkach nie ma już przepływu przez tę krawędź i możemy stwierdzić, że | F s , t | ≤m.[ti+1,tj−1]|Fs,t|≤m
(*) Dlaczego poprzednie twierdzenie jest prawdziwe? Cóż, każdy inny przepływ ścieżka w zaczyna się przed t i + 1 i kończy się po t j - 1 . Dlatego muszą nakładać się na siebie w czasie, gdy używają określonej krawędzi. Ponieważ przepływ jest zmaksymalizowany dla przepływu ścieżki, musi istnieć krawędź tam, gdzie jest ciasno.Fti,tjti+1tj−1
∑i,j∈[k]|Fi,j|≤cm3c