Mengapa kompleksitas pembatalan siklus negatif ?

Kami ingin menyelesaikan masalah aliran biaya minimal dengan algoritma pembatalan siklus negatif generik. Artinya, kita mulai dengan aliran acak yang valid, dan kemudian kita tidak memilih siklus negatif "baik" seperti siklus biaya rata-rata minimal, tetapi menggunakan Bellman-Ford untuk menemukan siklus minimal dan menambah sepanjang siklus yang ditemukan. Misalkan adalah jumlah node dalam grafik, jumlah sisi, kapasitas maksimal sisi dalam grafik, dan biaya maksimal sisi dalam grafik. Kemudian, materi pembelajaran saya mengklaim:$V$$A$$U$$W$

• Biaya maksimal di awal bisa tidak lebih dari$AUW$
• Augmentasi sepanjang satu siklus negatif mengurangi biaya setidaknya satu unit
• Batas bawah untuk biaya minimal adalah 0, karena kami tidak mengizinkan biaya negatif
• Setiap siklus negatif dapat ditemukan di$O(VA)$

Dan mereka mengikuti dari situ bahwa kompleksitas algoritma adalah . Saya memahami logika di balik setiap klaim, tetapi berpikir bahwa kompleksitasnya berbeda. Secara khusus, jumlah augmentasi maksimum diberikan oleh satu unit aliran per augmentasi, menjadikan biaya dari menjadi nol, memberi kami maksimal augmentasi AUW . Kita perlu menemukan siklus negatif untuk masing-masing, jadi kita mengalikan jumlah maksimum augmentasi dengan waktu yang dibutuhkan untuk menemukan siklus ( VA ) dan tiba di O (A ^ 2VUW) untuk algoritma.$O(V^2AUW)$$AUW$$AUW$$VA$$O(A^2VUW)$

Mungkinkah ini kesalahan dalam materi pembelajaran (ini adalah teks yang disediakan oleh profesor, bukan catatan siswa dari kursus), atau apakah logika saya salah?

$O( A^2 \cdot VUW)$