PRoblem

傳送門

Mean

最小化招聘給定不同類型志愿者，以滿足每日不同人數(shù)要求的費用總和。

Analysis

由線性規(guī)劃轉(zhuǎn)化為最小費用最大流來處理。 一般按如下步驟進行操作： ①添加松弛變量，將不等號都變?yōu)榈忍?。分別用下一個式子減去上一個式子，如果每個變量只出現(xiàn)了兩次且符號一正一負，那么可以轉(zhuǎn)化為費用流。 ②對于每個式子建立一個點，那么每個變量對應(yīng)一條邊，從一個點流出，向另一個點流入。 ③對于等式右邊的常數(shù)C，如果是正的，對應(yīng)從源點向該點連一條流量C，費用0的邊；如果是負的對應(yīng)從該點向匯點連一條流量?C，費用0的邊。 ④對于每個變量，從它系數(shù)為正的式子向系數(shù)為負的式子連一條容量為INF，費用為它在目標函數(shù)里系數(shù)的邊。 這樣網(wǎng)絡(luò)流模型就構(gòu)造完畢了。

Code