※ 引述《denehs (DE)》之銘言：
: ※ 引述《JonathanWang (小尹)》之銘言：
: : 這題想不出來的話可以用 mincost maxflow, 有流量下界的那種來解
: : worst case: 流量 10, node 約 10000, edge 約 1000000
: : 要做 10 次有負邊最短路徑, 而這種圖非常特別, 或許有什麼很快的求法
: edge要怎麼對應??
1 2 1 3 4 2 1
/ CD1 = - = - - - = \
source - CD2 - = - - - = - - sink
\ CD3 - - - = - - - /
\ CD4 - - - - = - - /
= 是有下界的 edge
然後在每個 step 之間加上 edge, cost 為 1 表示換 CD 片
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.20
※ 編輯: JonathanWang 來自: 140.112.30.20 (11/08 15:04)