Uvaoj 11248 Frequency Hopping(Dinic求最小割)

題意：1到n節點（節點之間有一定的容量），需要流過C的流量，問是否可以？如果可以輸出possible， 否則如果可以擴大任意一條邊的容量

可以達到目的，那麼輸出possible option：接着輸出每一條可以達到目的的邊（按升序），再否則輸出not possible

思路：先求一次最大流，如果流量至少為C，則直接輸出possible，否則需要修改的弧一定在最小割裡！

接着吧這些弧（最小割裡的）的容量設為無窮大，然後在求最大流，看最大流的流量能否滿足是C即可，如果滿足了，那就把這一條邊記錄下來

分析：最大流的程式沒有必要完全的執行完畢，知道目前的流量>=C那麼就可以中止最大流的程式！

還有就是第一次的最大流程式如果沒有找到>=C的最大流，那麼此時的流量留着，下一次在最小割裡擴容的時候，總是接着第一次Dinic的流量

繼續尋找....

<a></a>

本文轉自 小眼兒 部落格園部落格，原文連結：http://www.cnblogs.com/hujunzheng/p/4014923.html，如需轉載請自行聯系原作者