使用Dinic的O((V^2)E)算法比Edmond-Karp算法O(V(E^2))有什么优势吗？换句话说，我想知道如果从竞争性编程的角度来看，O((V^2)E)比O(V(E^2))好在哪里？
比方说，顶点总数为n。"通常"，连接图的边数往往在n和n^2之间。
大多数情况下，输入图不是很稀疏，所以在最大比例的情况下，边的数量会大于n（可能是O(n log n)，或者在最坏的情况下，O(n^2)）。
所以，如果你考虑最坏的情况，O(V^2 * E)是O(n^4)，而O(V*E^2)是O(n^5)。因此你看到了使用O(V^2*E)时间算法比O(V*E^2)的优势。