3597: 最小密度路径-训练套题T1T4
Memory Limit：128 MB
Time Limit：2.000 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：2
Description
4. 最小密度路径[path.pas/ path.c/ path.cpp]
【问题描述】
这次的任务很简单，给出了一张有N个点M条边的加权有向无环图，接下来有Q个询问，每个询问包括2个节点X和Y，要求算出从X到Y的一条路径，使得密度最小（密度的定义为，路径上边的权值和除以边的数量）。
【输入数据】
第一行包括2个整数N和M。
以下M行，每行三个数字A、B、W，表示从A到B有一条权值为W的有向边。
再下一行有一个整数Q。
以下Q行，每行一个询问X和Y，如题意所诉。
【输出数据】
对于每个询问输出一行，表示该询问的最小密度路径的密度（保留3位小数），如果不存在这么一条路径输出“OMG!”（不含引号）。
【输入样例】
3 3
1 3 5
2 1 6
2 3 6
2
1 3
2 3
【输出样例】
5.000
5.500
【数据规模】
对于60%的数据，有1 ≤ N ≤ 10，1 ≤ M ≤ 100，1 ≤ W ≤ 1000，1 ≤ Q ≤ 1000；
对于100%的数据，有1 ≤ N ≤ 50，1 ≤ M ≤ 1000，1 ≤ W ≤ 100000，1 ≤ Q ≤ 100000。
HINT
问题简述：
给一个有向无环图，求任两点间距离除以边数的最小值。
问题分析：
考虑转化成我们熟悉的问题解决。
由于都是求最小，很容易想到和此题类似的一个问题，求任两点间的最短路，能否借鉴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)}。