[HNOI2009]最小圈[0/1分数规划,SPFA]

题面

标题比题面好懂系列. 题目就是要求所有环中边权之和与环长之比的最小值.

令点权为1(方便统计长度. 更一般的0/1分数规划题中点权是可以任意取的, 后续推导一致), 则

$latex ans=\sum{e.w}/\sum{v.w}$

$latex \sum{e.w}-ans*\sum{v.w}=0$

$latex \sum(e.w-ans*v.w)=0$

$latex \sum_{i=1}^{k}(e_i.w-ans*v_i.w)=0 (e_k,v_k\text{在环上})$

$latex \sum_{i=1}^{k}(e_i.w-ans)=0$

然后就可以二分ans(实数域上)

chk(mid): 图以$latex e_i-mid$为边权, 若存在一个负环, 即存在一组位于一个环上的k个数使 $latex \sum_{i=1}^{k}(e_{i}.w-mid)<0$(对于更一般的0/1分数规划, i可以取任意值, 也可以选任意多个值, 这时选所有使$latex e_{i}.w-mid*v_{i}$为正的数即可判断”负环”存不存在/答案可不可行), 则有

$latex \sum e.w<mid*\sum v.w$

$latex mid>\sum e.w/\sum v.w$

即 mid>ans , 则mid要变小, r=mid

注意找负环要用dfs的SPFA, 存在负环时它会绕圈.

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址