简介

本文涵盖以下内容:

  1. 缩点
  2. 割点
  3. 点双连通分量
  4. 边双连通分量
阅读全文 »

简介

大概就是最大化/最小化这么一个东西:

有一堆物品,每个物品有价值c和容量w,选择一部分物品最大化 $\frac{\sum{c_i}}{\sum{w_i}}$

我们二分最大值,然后这样判断 $\frac{\sum c_i}{\sum w_i}\ge k\Rightarrow \sum c_i-k*\sum w_i\ge 0$

阅读全文 »