Dlaczego złożoność ujemnego anulowania cyklu ?

Chcemy rozwiązać problem minimalnego przepływu kosztów za pomocą ogólnego algorytmu anulowania cyklu ujemnego. Oznacza to, że zaczynamy od losowego prawidłowego przepływu, a następnie nie wybieramy żadnych „dobrych” cykli ujemnych, takich jak cykle o średnich kosztach minimalnych, ale używamy Bellman-Ford do odkrycia minimalnego cyklu i zwiększenia wzdłuż odkrytego cyklu. Niech będzie liczbą węzłów na wykresie, liczbą krawędzi, maksymalną pojemnością krawędzi na wykresie, a maksymalnymi kosztami krawędzi na wykresie. Następnie moje materiały do ​​nauki twierdzą:$V$$A$$U$$W$

• Maksymalne koszty na początku nie mogą przekraczać$AUW$
• Powiększenie w jednym cyklu ujemnym zmniejsza koszty o co najmniej jedną jednostkę
• Dolna granica kosztów minimalnych wynosi 0, ponieważ nie zezwalamy na koszty ujemne
• Każdy cykl ujemny można znaleźć w$O(VA)$

Z tego wynika, że ​​złożoność algorytmu wynosi . Rozumiem logikę każdego z tych twierdzeń, ale uważam, że złożoność jest inna. W szczególności, maksymalna liczba augmentacji jest podana przez jedną jednostkę przepływu na augmentację, koszty z do zera, dając nam maksimum augmentacji . Musimy odkryć cykl ujemny dla każdego, więc mnożymy maksymalną liczbę augmentacji przez czas potrzebny do wykrycia cyklu ( ) i do dla algorytmu.$O(V^2AUW)$$AUW$$AUW$$VA$$O(A^2VUW)$

Czy może to być błąd w materiałach do nauki (jest to tekst dostarczony przez profesora, a nie notatki studenta z kursu), czy też moja logika jest błędna?

Według TopCodera poprawny czas działania to .$O( A^2 \cdot VUW)$