最後一題 最小費用最大流。

其實這題算 最大費用最大流,要用到一個蠻常見的建模方法 - 拆點。

把 每個點拆成 2點(a, b),建兩條邊。

因為每個分數只能拿一次 ,(a, b, 1, -v[i][j])。

剩下可以走最多 k 次,(a, b, INF, 0)。

然後跟相鄰可走的點(a2, b2),(b1, a2, INF, 0)。

再建 S,(S, 1, INF, 0)。

答案就求 -MCF(S, n*n*2, k),最小加 "-" 就變最大了。

http://codepad.org/q697LHGd

p.s: 1A 有點爽XD。

 

 

 

文章標籤
創作者介紹

jghs1328

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