ネットワーク フローの問題は、線形計画法に帰着できることは誰もが知っています。ただし、ネットワーク フローの問題を解決する場合、フローは常に整数である必要があります。したがって、ネットワークフローは整数線形計画法に縮小する必要があると思います。NP 完全な ILP のおかげで、ネットワーク フローの問題も NP 完全な問題になるはずです。しかし、ネットワーク フローの実行時間は O(Cm) であるため、これは学んだことと矛盾します。どこが間違っていますか？ネットワークフロー問題の実行時間がナップザック問題(Wn)のように疑似多項式時間だからでしょうか? 私は今とても混乱しています！