PRoblem

傳送門

Mean

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

Analysis

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

Code