笔记 - 0/1分数规划

题目

• 放弃测试 模板 0/1 分数规划

• sightseeing cows 典 0/1 分数规划 + SPFA判负环
  这题好像不能用 dinkelbach迭代法

• 沙漠之王 典 0/1 分数规划 + Prim

  关于 dinkelbach 迭代法完虐二分法的这件事

  《进阶指南》中关于 0/1分数规划介绍的末尾, 挖了个 dinkelbach算法 的坑
  我遂网上冲浪了一下, 找到了这篇

  有多快

  在 放弃测试 中, dinkelbach 以五倍的速度完虐二分法
  在此题也同样稳定地五倍吊打着
  

  核心思想

  (我讲不好..具体看上面的那篇博客)
  函数 \(f(x)=\sum A_ic_i-x\sum B_ic_i\) 其实是个直线
  求出 \(x\) 对应的 \(f_{x_{max}}\) 后, 二分算法仅仅判断了\(f_{x_{max}}\) 与 \(0\) 的关系
  但其实将 \(f_{x_{max}}\) 利用起来, 找到 \(f_{x_{max}}\) 所在的那条直线, 然后将 \(x\) 移到这条直线的截距上去, 就可以实现极速定位

  代码

  double dinkelbach(){             
      double x=0, ans, p, q;
      while(true){
          ans=x, p=0, q=0;
          REP(i, 0, n) dis[i]=INF, vis[i]=false; dis[1]=0;
          
          REP(_, 1, n){                           // Prim O(N^2)
              int u=0;
              REP(v, 1, n) if(!vis[v] && dis[v] < dis[u]) u=v;
              vis[u] = true;
              if(u!=1) p += c[pre[u]][u], q += d[pre[u]][u];
  
              REP(v, 1, n) if(!vis[v] && dis[v] > c[u][v]-d[u][v]*x)
                  dis[v] = c[u][v]-d[u][v]*x, pre[v]=u;
          }
          x = p/q;                                // 直接移动到截距上
          if(fabs(ans-x)

  但似乎 dinkelbach 并不能完全取代二分, 可能在某些场景前者并不适用, 所以最好两种方法都掌握.
  迭代法不适用的场景之一: 0/1分数规划 + SPFA判负环