题意
做法
令(l_{u,v}((u,v)in E))为边((u,v))的边权
令(x_{u,v})为对边((u,v))的增量
令(X)为总增量限制
令(d_i)为一组增量序列({x})对图造成影响后，从(s)到(i)的最短路径
可以发现(d_s)是什么并不重要，我们将其写成线性规划的形式
[\
max(d_t-d_s)\
left{egin{array}{}
d_vle d_u+l_{u,v}+x_{u,v}\
sumlimits_{(u,v)in E}x_{u,v}le X\
x_{u,v}ge 0\
end{array}
ight.
]
二分(d_t-d_sge lambda)来判断答案
[\
min(sumlimits_{(u,v)in E}x_{u,v})\
left{egin{array}{}
d_vle d_u+l_{u,v}+x_{u,v}\
d_t-d_sge lambda\
x_{u,v}ge 0\
end{array}
ight.
]
发现这个其实就是(min(max(lambda +d_s-d_t,0)cdot infty+sumlimits_{(u,v)in E}max(d_v-d_u-l_{u,v},0)cdot 1))
于是我们对偶到最大循环费用流上
我们求网络流是流量都为整数，你可能会想为什么整数解就一定会有最优解，放心写吧，这个定理貌似就是这样的
(slongrightarrow t(flow:infty,cost:lambda))
(vlongrightarrow u(flow:1,cost:-l_{u,v})((u,v)in E))
不考虑第一类边，对(tlongrightarrow s)跑最大费用流，令流量为(i)时费用为(f_i)，则总费用为(ilambda+f_i)
则最大循环费用流为(max(ilambda +f_i))，需要满足(le X)，即(lambdale frac{X-f_i}{i})，于是我们发现不用二分了
由于题目保证没有重边，故最大流量是(O(n))的，询问是枚举(i)即可