假設我f在流網路上獲得了一些映射，表示為每條邊上流的稀疏矩陣。是否有可能驗證此映射確實是多項式時間內的流？
即它需要滿足
- 流網路中的每條邊都被分配一個小于容量的正數
- 進入節點的邊等于離開節點的邊
如果我要在這個流網路上進行 BFS，我擔心我可能會遇到這樣的問題，即對于 DAG 中的每條邊，我都需要遍歷每條傳出邊，我不確定這是否需要指數時間或不。這可以在多項式時間內完成嗎？
uj5u.com熱心網友回復：
我認為您可以在 O(V E) 時間內完成：
對于每個頂點，在 0 處
v創建一個計數器counter_v。對于每條邊
e，檢查f(e)<= c(e)（流量小于容量）。如果不是這種情況，你就完成了，這不是一個有效的流程。否則，e從v1 -> v2您開始按流遞減 v1 的計數器，并按流遞增 v2 的計數器：counter_v1 -= f(e); counter_v2 = f(e)對于 和 以外的每個頂點
s，t檢查計數器是否為 0，即通過該頂點的總流量為 0。
就是這樣，你檢查了每個頂點兩次，每條邊檢查一次，所以 O(V E)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/452517.html