将所有边权减去k，问题转化为求平均边权绝对值的最小值,这是显然的。
那么考虑二分一个mid，表示最小值，有则$ -mid < \overline{w_i}<mid $
则 −mid<sumi+sumjdepi+depj<mid-mid<\dfrac{sum_i+sum_j}{dep_i+dep_j}<mid−mid<depi+depjsumi+sumj<mid
易知，depi+depj>0dep_i+dep_j>0depi+depj>0，则只需对于 sumi+sumjsum_i+sum_jsumi+sumj 的正负进行讨论，以 sumi+sumj>0sum_i+sum_j>0sumi+sumj>0 的情况为例：
sumi+sumj<mid(depi+depj)sum_i+sum_j<mid(dep_i+dep_j)sumi+sumj<mid(depi+depj)
sumi−mid×depi<mid×depj−sumjsum_i-mid\times dep_i<mid\times dep_j - sum_jsumi−mid×depi<mid×depj−sumj
标签：汽水,P6670,边权,mid,sumj,sumi,2016 From： https://www.cnblogs.com/happy-XQJ/p/17360064.html