題目網址: http://poj.org/problem?id=2391
題意: 農場有F個區塊，每個區塊會有A隻牛B個避雨棚，且有P條無向的路連接某兩個區塊且給定此路徑所需時間，問所有的牛都能避雨最快所需時間，或無法全部避雨。
解法: 可以當成給定時間，確定此時間內是否可行，若行，則代表大於此時間的都行，所以答案有單調性值，可以使用二分查找來找答案，可以先使用Floyd找出所有任兩點間最短路徑，用二分查找最長路徑與0間最小符合最大流等於牛總數，建圖方式從S到每個區塊i增加一條有向邊容量為此區塊的牛數量，再建立每個區塊i至區塊i'一條有向邊容量為無窮大，最後再增加區塊i至區塊j'一條容量為無窮的有向邊，若區塊i至區塊j的最短路徑小於當前查找的時間。
TAG: Floyd Warshall, Binary Search, Flow Network, MaxFlow, Dinic
注意:
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽