作者JonathanWang (小尹)
看板ACMCLUB
标题Re: 即时战况
时间Mon Nov 8 13:21:51 2004
※ 引述《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)