frankchenfu 的博客

frankchenfu 的博客

题解 CF187B 【AlgoRace】

posted on 2018-04-06 15:37:22 | under 题解 |

我们考虑动态规划。


假设我们已经知道了

  • $i\to j$只用第$k$部车的最短时间为$g_{i,j,k}$;
  • 并且设$f_{i,j,p}$表示$(i,j)$换$p$次车的最短时间。

于是我们考虑使用Floyd算法,可以得到转移方程:

$$f_{i,j,p}=\displaystyle\min_{k}^{k\in V}\{f_{i,k,p-1}+f_{k,j,0}\}$$

这是什么意思呢?一般的Floyd在进行松弛操作的时候,并不需要考虑这里的$p$,而在这里,我们发现每次松弛操作的时候,都需要“换一次车”。这也就意味着,如果我们要求换$p$次车的最小值,一定是换$p-1$次车之后,再换一次车。而前$p-1$次换车对应的就是$i\to k$,而最后再换一次车$k\to j$。

这样,我们通过$1000$次(询问中$k$的最大值)Floyd就可以求出答案了。那么$g_{i,j,k}$怎么求呢?很简单,读入之后做$m$次Floyd即可。这样这个算法就结束了,时间复杂度为$O(k_{\max}\cdot n^3)=2.16\times 10^8$,看起来勉强可以通过2000ms的实现,然后最后我TLE 36了(加上优化之后仍然TLE 53).所以我们有没有什么好的办法进一步优化呢?


其实算法上并不需要优化! 我们注意到因为只有$60$个城市,所以换车次数不会超过$60$,那么我们把$k_{\max}$就可以可看做是$60$,于是$O(k_{\max}\cdot n^3)=60^4=1.296\times 10^7$.于是就很愉快地通过了。


#include<cstdio>
#include<cstring>
#include<assert.h>
#define NDEBUG
const int MAXN=65,MAXK=1010;
const int MAXQ=100010;
int n,m,r,max_k=1<<31;
int f[MAXN][MAXN][MAXK],g[MAXN][MAXN][MAXN];
int q[MAXQ][3];
//f_{i,j,k}=(i,j)换k次车. g_{k,i,j}=(i,j)用第k种车直接跑.

inline int max(int x,int y){
    return x>y?x:y;
}
inline int min(int x,int y){
    return x<y?x:y;
}
int main(){
//  freopen("test.in","r",stdin);
    scanf("%d%d%d",&n,&m,&r);
    for(int k=1;k<=m;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&g[k][i][j]);
    for(int i=1;i<=r;i++){
        scanf("%d%d%d",&q[i][0],&q[i][1],&q[i][2]);
        max_k=max(max_k,q[i][2]);
    }
    max_k=min(max_k,n);

    //floyd O(m* n^3)=O(n^4)=1.296e+7;
    for(int p=1;p<=m;p++)
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    g[p][i][j]=min(g[p][i][j],g[p][i][k]+g[p][k][j]);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f[i][j][0]=~(1<<31);
    for(int k=1;k<=m;k++)//初值:不换车,从头跑到尾.
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[i][j][0]=min(f[i][j][0],g[k][i][j]);

    for(int p=1;p<=max_k+1;p++){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[i][j][p]=f[i][j][p-1];
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    f[i][j][p]=min(f[i][j][p],f[i][k][p-1]+f[k][j][0]);
    }

    for(int i=1;i<=r;i++){
        q[i][2]=min(q[i][2],max_k);
        printf("%d\n",f[q[i][0]][q[i][1]][q[i][2]]);
    }
    return 0;
}