作者JonathanWang (小尹)
看板ACMCLUB
标题Re: 即时战况
时间Mon Nov 8 12:31:22 2004
※ 引述《CorruptAngel (微笑面具)》之铭言：
: We did so too:(
: but we still wrote a greedy search and got WA.
: ※ 引述《denehs (DE)》之铭言：
: : I create a 1-D array to record when is the next time the DVD will be
: : requested,and if it won't appear again,give it a value 110 (because the
: : max length is 100),and got WA....><..
: : We though that greedy was an incorrect algorithm,so didn't debug.......
: : (chinese typing crashed...XD)
这题想不出来的话可以用 mincost maxflow, 有流量下界的那种来解
worst case: 流量 10, node 约 10000, edge 约 1000000
要做 10 次有负边最短路径, 而这种图非常特别, 或许有什麽很快的求法
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.20