图论内容：

1.判断负环：

• 在SPFA基础上加cnt[]记录每个点的最短路条数，如果cnt[i] >= n则存在负环
• 优化：
  • 当SPFA迭代的总边数大于 边数的2倍，可认为存在环（经验上的trick）
  • 队列超时的情况下可改为栈，更快的找到负环

2.01分数规划

• 求 wi / si 最大，结合二分 使得 $ wi/si>mid $ , 移项得$ wi− si * mid > 0 $ , $ wi− si * mid > 0 $ <–> 图中存在正环

3.差分约束

• 转化为图论最短路问题,如SPFA最短路中更新完后满足dist[j] <= dist[t] + w[i],是不是很像 x[j] <= x[i] + c
  • 最小值求最长路，最大值求最短路
  • 可增加超级源点（等价于初始时将所有点加入队列中）

基本算法

1.单调队列

• 单调栈是单调队列的特殊形式，一端封闭
• 队列存的是下标
• 一般与前缀和 结合起来，模板题最大子序和