PRoblem

傳送門(mén)

Mean

某汽車(chē)維修中心有m位技術(shù)人員，有n輛汽車(chē)待修理。 不同的技術(shù)人員修理不同車(chē)輛耗時(shí)不同。 最小化平均等待時(shí)間。

Analysis

經(jīng)典的最小費(fèi)用最大流。 設(shè)第j位技術(shù)人員修理第i輛汽車(chē)耗時(shí)為w[i,j] 。 將技術(shù)人員拆成n個(gè)點(diǎn)，每個(gè)點(diǎn)向汽車(chē)連容量為1的邊，第k個(gè)點(diǎn)所連邊費(fèi)用為k×w[i,j]，表示倒數(shù)第k個(gè)修理該車(chē)則對(duì)總等待時(shí)間貢獻(xiàn)k×w[i,j]。 再由源點(diǎn)想技術(shù)人員，汽車(chē)向匯點(diǎn)分別連容量為1， 費(fèi)用為0的邊即可。

Code