不难看出这是一道差分约束的题目。
但是如果想按照通常的题目那样去建边的话，就会发现这句话——相邻两站的距离至少是1公里——建边后就直接让整个题出现了负环(默认是按求最短路建边)，没法做了。
这时我们就需要使用断环为链的技巧。
可以设\(len\)为地铁环线总长
那么就需要把\(a→b(a>b)\)的限制条件转换为\(b→a\)的限制条件，比如\(dis(a,b)\leq k\)转换为\(dis(b,a)\geq len-k\)。总算能连边建图惹
如果现在要判断是否有解，那方法肯定是\(spfa\)判负环。
但问题在于\(len\)是未知量，如果用\(len\)表示每一条边，那么\(e_i=len\pm d_i\ or\ \pm\ d_i\)。
因为有没有解的关键在于有没有负环，所以：
考虑图上每一个环, 其权值一定可以表示为 \(val=k×len+b\) 的形式. 那么现在分类讨论一下每一个环.
- \(k=0\) 且 \(b<0\) 时, \(val<0\)，为负环,一定无解；
- \(k<0\) 且 \(b<0\) 时, \(val<0\)，为负环,一定无解；
- \(k<0\) 且 \(b>0\) 时, 如果出现\(val<0\)，可以通过减小 \(len\) 来消除负环；
- \(k>0\) 时, 如果出现\(val<0\)，可以通过增大 \(len\) 来消除负环。
这样思考会发现\(len\)的合法大小一定是一段连续区间
所以可以确定一个\(INF\)，然后二分\(len\)，由上述规律找到\(len\)的合法区间的左右端点，如果右端点接近\(INF\)则判断为无数个解。
\(tips\)：
- 凡是没有说明联通的图都要小心；
- 可能只有一个点；
- 因为\(e_i=len\pm d_i\ or\ \pm\ d_i\)，而\(len\)是变量，所以建边的时候存\(len\)的系数和\(d_i\);
- 若一个点入队次数超过n,则有负权环,然后要判断\(k\)的值，来决定二分方向，要记录来时的边
废话，并且把环取出来 可能有小尾巴呀；
代码:
#include
#include
参考了的博客
我也不知道他 blog 为啥没了，也不敢问