假設右圖為某石油公司輸送網路圖，A、B、C、D代表輸送控制站，圓點和圓點之間箭頭代表流向，其上數字代表容量，每個輸送控制站的輸入量等於輸出量，請問從北部到中部可輸送的最大流量為下列何者？
A14正確答案
B15
C17
D19
答案與詳解
為什麼答案是 A
最大流=最小割=14。從圖結構分析：S出發有兩條邊S→A(15)和S→B(4)，S→B僅4，而到T的邊C→T(7)和D→T(10)合計17，但中間瓶頸限制了最大流為14。
考點：最大流最小割考點：單邊容量誤判考點：終點容量誤判考點：起點容量誤判
載入中…
