洛谷 P1730 最小密度路径 题解【Floyd】【DP】

点击量：174

   Floyd的一个简单变形。

目录

题目描述

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

 

输入输出格式

输入格式：

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

 

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

 

再下一行有一个整数Q。

 

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

 

输出格式：

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

 

输入输出样例

输入样例#1：

3 3

1 3 5

2 1 6

2 3 6

2

1 3

2 3

输出样例#1：

5.000

5.500

说明

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

题解：

   因为我们要找路径权值和除以长度最小的路径，根据贪心我们知道，这条路径的本质就是最短路。而$ n\le 50$就可以很方便的用floyd转移，而这个题不会这么简单，而是要套一个类似动态规划的转移。

   在floyd转移过程中，我们用f[i][j][k]表示从i到j走过长度（不是权值）为k的最短路。而在原来转移时，有$ O(n^3)$的复杂度，但我们如果要枚举左边几条边，右边几条边，复杂度就是$ O(n^3m^2)$了，当然不合理。不过这种思路当然是对的，我们要想办法优化它。

   其实这种情况下只需要枚举m次就可以了。当u和v的最短路权值和一定时，用f[i][j][l]=f[i][k][p]+f[k][j][l-p]更新，和用f[i][j][l]=f[i][k][l-1]+f[k][j][1]是一样的，因为插的点k是不同的，因此总能更新出一定长度的最短路。类似一条长度为t的最短路，这条最短路可以由对于任意一个i的左数第i个点+右数第l-i个点转移，总是能转移到的。那么我们转移f[i][k][p-1]和f[k][j][1]是最方便，也是最直观的，同时也避免了最优解的路径长为1的问题，那么我们这时只需要枚举m次。时间复杂度为$ O(n^3m)$。

   注意使用浮点型数据类型。

Code：

#include<cstdio>
#include<cstring>
int min(int x,int y)
{
    return x<y?x:y;
}
double min(double x,double y)
{
    return x<y?x:y;
}
int f[55][55][1010];
int main()
{
    memset(f,0x3f,sizeof(f));
    int n,m,u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        f[i][i][0]=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        f[u][v][1]=min(f[u][v][1],w);
    }
    for(int l=1;l<=m;l++)
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    f[i][j][l]=min(f[i][j][l],f[i][k][l-1]+f[k][j][1]);
    int q;
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d",&u,&v);
        double ans=123456789123456.0;
        for(int i=0;i<=m;i++)
            if(f[u][v][i]!=0x3f3f3f3f)
                ans=min(ans,f[u][v][i]*1.0/i);
        if(ans==123456789123456.0)
            puts("OMG!");
        else
            printf("%.3lf\n",ans);
    }
    return 0;
}