【算法】二分+spfa

【题解】据说这个叫分数规划？

0-1分数规划

二分答案a，则对于任意的环有w/k≤a即w-ak≤0，若满足条件则a变小，否则a变大。

因为w=w₁+w₂+...+w_k，所以变形为(w₁-a)+(w₂-a)+...+(w_k-a)≤0。于是问题转化为在图中找负环。

不过由于spfa限制，“=”没办法并入"<"，但是由于精度足够，最后也就是1.00000000001≈1.00000000。

使用DFS的spfa：可以在发现更新到之前更新过的节点就认为是负环(从x跑出去最后又回来更新x，说明跑的这段路是负数)。

确认某个曾访问的节点是祖先，这是DFS的特性和优势。

精度问题：10⁷要求精确到10^-8即log(10¹⁵)/log(2)=49，所以跑60次二分就能保证精度没问题了。

http://hzwer.com/5766.html

【BZOJ】1486 [HNOI2009]最小圈