題目網址: http://poj.org/problem?id=3680
題意: 給定N個帶權重Wi的開區間，求開區間重疊不超過K個的最大權重總和。
解法: 先將給定區間的值離散化，將離散化後的每個值當成一個點，且額外增加一起點S、一終點T，然後在(S,V1),(V1,V2)...(VN,T)建立有向邊且容量為K權重為0，接著在每個開區間(Vi,Vj)建立有向邊容量為1權重為-Wi，接著以此圖求最小費用最大流，輸出負的最小費用即可。
TAG: MinCostMaxFlow, 離散化
注意: 網路流的題目都要非常注意點、邊的數目所需分配的空間。
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽