我們可以找到一種算法來計算(線性時間)樹狀網絡的最大流量,也就是說,對於網絡中的水槽(及其相關邊)的去除留下一個樹。計算網絡的最大流量
0
A
回答
0
Ford-Fulkerson是O(E * f)其中E是邊的數量並且f是最大流量,如果在問題中對E或f有一個恆定的上界,那麼將被認爲是線性的。
2
是的,只需要運行類似如下:
maxf(s) {
if (s == sink) return s.in_capacity;
ret = 0;
foreach(c in children(s)) ret += maxf(c);
return min(ret, s.in_capacity);
}
使用與S等於源(我們假設源具有無限的in_capacity)的初始呼叫。
+0
該算法似乎是正確的。這只是「無行爲能力」,我沒有得到 – conapart 2010-11-23 10:03:45
相關問題
- 1. 查找任何網絡的最大流量由給定的算法
- 2. 計算GPRS網絡中的收費流量
- 3. 網絡的最大流量是不是唯一的
- 4. 泊塢窗統計網絡流量
- 5. 測量WCF網絡流量
- 6. 最大流量
- 7. 算法問題:轉換非整數最大流量到整數最大流量
- 8. 通過使用最大流量算法
- 9. 計算最大
- 10. 計算最大值的數量
- 11. 計算最節能的ad-hoc網絡的算法
- 12. 網絡流量的流壓縮
- 13. Selenium - 等待網絡流量
- 14. XMPP網絡流量分析
- 15. google雲vps網絡流量
- 16. 記錄網絡流量
- 17. Java保護網絡流量
- 18. 網絡流量:對或錯
- 19. 分析網絡流量
- 20. libpcap網絡流量攔截
- 21. C# - 捕獲網絡流量
- 22. iPad - 監控網絡流量
- 23. 神經網絡值計算?
- 24. Python網絡/ cidr計算
- 25. 計算B類網絡中每個子網的主機數量
- 26. 網站的流量估算
- 27. 算法找到最小削減給定的最大流量
- 28. 最大流程圖算法
- 29. 貪婪的最大流量
- 30. 在C中測量網絡流量#
如果圖靈機中的狀態數量有一個恆定的上限,則暫停問題是O(1)。所有你需要知道的是BB(| S |),其中| S |是州的數量。 – 2010-11-26 04:54:28