POJ 1087 A Plug for UNIX(網絡流之最大流)
題目地址:POJ 1087
不知道是誰把這題化為了二分最大匹配的專題裡。。於是也沒多想就按照二分圖的模型來建的(雖然當時覺得有點不大對。。。)。後來發現二分最大匹配顯然不行。。有權值。。直接來個最大流多方便。。然後一直WA。。後來仔細想了想。。這根本就不能建二分圖啊。。。。這題跟二分圖一點關系都沒有。。。。
這題的建圖思路是讓源點與每一個設備的插座類型連邊,讓匯點與每一個插座連邊。然後用floyd判斷該設備能否通過轉換轉換成可以插的插座上。只要可以轉換成的就連邊,權值為INF。然後求一次最大流,用n減去就行。
這題有個坑點,就是輸入的插座可能會重復。。。需要去重。
代碼如下:
#include
#include
#include
#include
#include
#include
#include
#include
#include