洛谷 P1730 最小密度路径

Description

给出一张有 \(N\) 个点 \(M\) 条边的加权有向无环图，接下来有 \(Q\) 个询问，每个询问包括 \(2\) 个节点 \(X\) 和 \(Y\)，要求算出从 \(X\) 到 \(Y\) 的一条路径，使得密度最小（密度的定义为，路径上边的权值和除以边的数量），若无法到达输出 "\(OMG!\)"。

Constraints

\(1 \le N \le 50\)，\(1 \le M \le 1000\)，\(1\le W \le 10^5\)，\(1 \le Q \le 10^5\)

Solution

考虑把密度的表达式表示出来，设最后答案密度为 \(r\) ，边数量为 \(e\)，边权为 \(w[1] , w[2] , w[3] , ... w[e]\)，则可列出等式

\(\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \cfrac{\sum_{i=1}^e w[i]}{e} - r = 0\)

则通分得

\(\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \cfrac{\sum_{i=1}^e w[i] - e \times r}{e} = 0\)

合并后则得

\(\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \cfrac{\sum_{i=1}^e (w[i] - r)}{e} = 0\)

\(e\) 也不为 \(0\) 所以

\(\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \sum_{i=1}^e (w[i] - r) = 0\)

现在可以看出，影响该式值的就是 \((w[i] - r)\)。

由于问的是最小值，可以考虑二分其中的 \(r\)，根据上式，把图中每条边都减去二分的 \(r\) 值，求出最短路判断上式的值与0的关系，若大于 \(0\) 则说明取小了，找右半区间，否则找左半区间即可。

注意这题的询问次数很多，而点数 \(n\) 与边数 \(m\) 乘积很小，所以要先预处理每一个点对的结果，在询问时 \(O(1)\) 回答询问。

若不预处理最差复杂度 \((80pts)\)：\(O(Qnmlogn)\)

预处理最差复杂度 \((100pts)\)：\(O({n^{2}}{m^{2}}logn)\)

Code：

// by youyou2007 in 2022.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include