自动搬运

查看原文

来自洛谷，原作者为

	似水年华 **

搬运于2025-08-24 21:28:25，当前版本为作者最后更新于2017-07-15 15:05:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

#问题简述

给一个有向无环图，求任两点间距离除以边数的最小值。

#算法分析

考虑转化成我们熟悉的问题解决。

由于都是求最小，很容易想到和此题类似的一个问题，求任两点间的最短路，能否借鉴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);//输出 
    }
}