蠻裸的一題,最小費用最大流,題目都告訴你了 "Minimum Cost" XD。

對於 k 種商品都做一次 MCF(minimum_cost_flow),再加總即是答案。

建圖:

建立 超級源點(S)、超級匯點(T)。

對於 每個提供商 建立一條 (S, i, offer[i], 0) 的邊。

對於 每個買家    建立一條 (j, T, need[j], 0) 的邊。

對於 提供商和買家 建立一條 (i, j, INF, cst[i][j]) 的邊。

<Rrom, To, Cap, Cost>

我的code

http://codepad.org/VX8R1cqx

p.s: 太久沒寫 MCF,寫有點慢= =。

 

文章標籤
創作者介紹

jghs1328

jghs1328 發表在 痞客邦 PIXNET 留言(0) 人氣()