Pourquoi la complexité de l'annulation du cycle négatif ?

Nous voulons résoudre un problème de flux à coût minimal avec un algorithme générique d'annulation de cycle négatif. Autrement dit, nous commençons avec un flux valide aléatoire, puis nous ne sélectionnons pas de «bons» cycles négatifs tels que des cycles de coût moyen minimal, mais utilisons Bellman-Ford pour découvrir un cycle minimal et augmenter le long du cycle découvert. Soit le nombre de nœuds dans le graphique, le nombre d'arêtes, U la capacité maximale d'une arête dans le graphique et W les coûts maximaux d'une arête dans le graphique. Ensuite, mon matériel d'apprentissage affirme:$V$$A$$U$$W$

• Les coûts maximaux au début ne peuvent être supérieurs à $AUW$
• L'augmentation le long d'un cycle négatif réduit les coûts d'au moins une unité
• La borne inférieure pour les coûts minimaux est 0, car nous n'autorisons pas les coûts négatifs
• Chaque cycle négatif se trouve dans $O(VA)$

Et ils en découlent que la complexité de l'algorithme est $O(V^2AUW)$ . Je comprends la logique derrière chacune des revendications, mais je pense que la complexité est différente. Plus précisément, le nombre maximal d'augmentations est donné par une unité de débit par augmentation, ce qui porte les coûts de $AUW$ à zéro, ce qui nous donne un maximum d' augmentations $AUW$ . Nous devons découvrir un cycle négatif pour chacun, donc nous multiplions le nombre maximal d'augmentations par le temps nécessaire pour découvrir un cycle ( $VA$ ) et arriver à $O(A^2VUW)$ pour l'algorithme.

Cela pourrait-il être une erreur dans le matériel d'apprentissage (c'est un texte fourni par le professeur, pas les notes d'un étudiant du cours), ou ma logique est-elle erronée?

Selon TopCoder, le temps de fonctionnement correct est .$O( A^2 \cdot VUW)$