[Luogu 1730]最小密度路径

Description

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

Input

第一行包括2个整数N和M。

以下M行，每行三个数字A、B、W，表示从A到B有一条权值为W的有向边。

再下一行有一个整数Q。

以下Q行，每行一个询问X和Y，如题意所诉。

Output

对于每个询问输出一行，表示该询问的最小密度路径的密度（保留3位小数），如果不存在这么一条路径输出“OMG!”（不含引号）。

Sample Input

3 3
1 3 5
2 1 6
2 3 6
2
1 3
2 3

Sample Output

5.000
5.500

Hint

1 ≤ N ≤ 50，1 ≤ M ≤ 1000，1 ≤ W ≤ 100000，1 ≤ Q ≤ 100000

题解

考虑转化成我们熟悉的问题解决。
由于都是求最小,很容易想到和此题类似的一个问题,求任两点间的最短路,能否借鉴 $Floyd$ 算法来解决呢?
本题不同点在于,还要除以一个边数。因为这个除法的缘故,使得 $Floyd$ 算法的最优子结构性质被破坏,假设存在路径 $i -> k -> j$,它的最小密度路径并不一定是 $i -> k$ 的最小密度路径加上 $k -> j$ 的最小密度路径。
例:设$[A, B]$表示路径的权值和为 $A$,通过了 $B$ 条边。假设从 $i -> k$ 存在着两条路径 $L1[2, 3]$以及 $L2[8, 10]$,从 $k -> j$ 存在着两条路径 $L3[1, 2]$以及 $L4[51, 100]$,很明显 $i -> k$ 的最小密度路径是 $L1$,$k -> j$ 的最小密度路径是 $L3$,但是 $i -> k -> j$ 的最小密度路径却是 $L1 + L4$。
有否办法去掉这个除法的影响?
回到问题特性,是有向无环图,一条路径最多只能经过 $N-1$条边,于是我们可以对边数进行枚举,即把答案的分母枚举了,剩下的就是让答案的分子最小化(答案是权值和/边数),这就回到我们熟悉的问题:求最短。
在 $Floyd$ 的基础上重新划分阶段定义状态:

第 $k$ 个阶段表示恰好通过 $k$ 条边两点间的最短路,这样的话最优子结构以及无后效性都满足($k$ 的阶段的最优取值一定需要靠之前阶段的最优值,当然也不可能影响到之前阶段的取值了。)
定义状态 $f(i,j,k)$表示从 $i$ 到 $j$ 恰好经过 $k$ 条边的最短路,类似$Floyd$ 的算法得出 $DP$ 方程:
$$f(i,j,k)=Min(f(i,h,g)+f(h,j,k-g))$$
这个方程是 $5$ 维的,会超时,如何减小维数呢?
考虑在何处重复决策。注意到 $f(i,j,k)$的选择路径 $V1-V2-...-Vk$,实际上我们只要找到这里的一个点决策即可,而不需每个点都判断过去。这样就很容易想到在最后一个点进行决策。
$f(i,j,k)=Min(f(i,h,k-1)+f(h,j,1))$。数据范围不大,询问比较多,考虑用 $dp$ 直接算出所有点对的答案.因为密度 =$val \over R$ 所以考虑 $f[x][y][R]$ 为 $x=>y$ 经过 $R$ 条边的最小值 ,$ans={f[x][y][R] \over R}$
状态转移为:
$$f[i][j][R]=f[i][k][R-1]+f[k][j][1]$$

 //It is made by Awson on 2017.10.30

 #include <set>

 #include <map>

 #include <ctime>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <cstdio>

 #include <string>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 using namespace std;

 int INF;

 const double eps = 1e-;

 int n, m, u, v, c;

 int f[][][];

 void work() {

     memset(f, /, sizeof(f)); INF = f[][][];

     scanf("%d%d", &n, &m);

     while (m--) {

     scanf("%d%d%d", &u, &v, &c);

     f[u][v][] = Min(c, f[u][v][]);

     }

     for (int l = ; l < n; l++)

     for (int k = ; k <= n; k++)

         for (int i = ; i <= n; i++)

         if (i != k)

             for (int j = ; j <= n; j++)

             if (j != k && j != i)

                 f[i][j][l] = Min(f[i][j][l], f[i][k][l-]+f[k][j][]);

     scanf("%d", &m);

     while (m--) {

     scanf("%d%d", &u, &v);

     if (u == v) {

         printf("%.3lf\n", 0.0); continue;

     }

     double ans = INF;

     for (int i = ; i < n; i++) if (f[u][v][i] != INF) ans = min(ans, (double)f[u][v][i]/(double)i);

     if (abs(ans-INF) <= eps) printf("OMG!\n");

     else printf("%.3lf\n", ans);

     }

 }

 int main() {

     work();

     return ;

 }

巴特西