「ZJOI2010」贪吃的老鼠-二分+最大流

发布于 2018-10-20  89 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「ZJOI2010」贪吃的老鼠-二分+最大流

Description

有 $m$ 个老鼠,$m$块奶酪,第$i$块奶酪耐久度为$p_i$,要求在时间$[l_i,r_i]$内吃完。第$j$个老鼠每秒可以吃$s_j$蛋糕。要求保证

  1. 在任一时刻,一只老鼠最多可以吃一块奶酪。
  2. 在任一时刻,一块奶酪最多被一只老鼠吃。

可以施加一次魔法,使得每块奶酪的$r_i$延长$T$,求最小的$T$。

Solution

很容易想到二分$T$.

$S$向蛋糕连边,容量为$p_i$。

考虑时间线上只会发生两种事件:一块蛋糕可以被吃或者一块蛋糕变质,而只有当发生了某种事件后老鼠吃蛋糕的状态才会改变。所以可以把时间划分为$2 \times m$段,每段时间内每个老鼠向它能吃的蛋糕连边,同时每个老鼠向$T$连$tim \times s_i$容量的边。

但是这样没有考虑题目要求的两个条件。

这时可以把老鼠吃的速度再拆点。把$S$从大到小排序做差分,老鼠到蛋糕的边容量为$d_i \times tim$。老鼠到$T$的容量为$i \times d_i \times tim$。这样当老鼠$x$吃了蛋糕$Y$,则$x~m$的点到$y$都会有$d_i$的流量。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「ZJOI2010」贪吃的老鼠-二分+最大流


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前, 相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!