题解 P1730 【最小密度路径】
问题简述
给一个有向无环图，求任两点间距离除以边数的最小值。
算法分析
考虑转化成我们熟悉的问题解决。
由于都是求最小，很容易想到和此题类似的一个问题，求任两点间的最短路，能否借鉴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)}。
参考程序
#include<stdio.h>
using namespace std;
#define INF 1000000000
int n,m,q;
int dis[60][60][1010];
int main()
{
int i,j,k,l;
scanf("%d %d",&n,&m);//读入
for(l=1;l<=m;l++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dis[i][j][l]=INF;//初始化
for(i=1;i<=m;i++)
{
long long a,b,w;
scanf("%lld %lld %lld",&a,&b,&w);
if(dis[a][b][1]>w)
dis[a][b][1]=w;//注意有重边的情况
}
for(l=2;l<=m;l++)
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(dis[i][j][l]>dis[i][k][l-1]+dis[k][j][1])
dis[i][j][l]=dis[i][k][l-1]+dis[k][j][1];//类似Floyd算法的DP
scanf("%d",&q);
while(q--)
{
int x,y;
double ans=INF,min=INF;
scanf("%d %d",&x,&y);//读入询问
for(l=1;l<=n;l++)
{
if(dis[x][y][l]<INF)
ans=double(dis[x][y][l])/double(l);
if(ans<min)
min=ans;
}//对边数进行枚举,算权值和/边数
if(min==INF)
printf("OMG!\n");
else
printf("%.3lf\n",min);//输出
}
}