P5152: 最小密度路径-训练套题T1T4
传统题
2.000s
时间限制
128MB
内存限制
4 提交
4 解决
【题目描述】
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。
【提示】
问题简述：
给一个有向无环图，求任两点间距离除以边数的最小值。
问题分析：
考虑转化成我们熟悉的问题解决。
由于都是求最小，很容易想到和此题类似的一个问题，求任两点间的最短路，能否借鉴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)}。