最小費用最大流。

建模不難想到,一個 超級源點(S) 和 超級匯點(T)。

S-> 每個M (S, i, 1, 0)

每個H -> T (j, T, 1, 0)

每個M -> 每個H (i, j, 1, abs(i.x-j.x)+abs(i.y-b.y))

<From, To, Cap, Cost>

我的code

http://codepad.org/phWWU47G

p.s: n 最大會到 100*100/2=5000,m 要到 n*n=25000000。

       開不夠大竟然會 TLE= =,原本以為卡 vector,辛苦改成 上面那個樣子= =。

       vector 版: http://codepad.org/TYZs4olc

 

 

文章標籤
創作者介紹

jghs1328

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