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

作者: wjyyy 分类: DP,最短路,解题报告 发布时间: 2018-07-20 21:09

点击量:20

 

   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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */