2016计蒜之道复赛 百度地图的实时路况 floyd+cdq分治

时间：2021-09-15 09:53:36

链接：https://nanti.jisuanke.com/t/11217

奉上官方题解：

枚举 d(x , y , z) 中的 y，把 y 从这个图中删去，再求这时的全源最短路即可，使用 Floyd 算法来做上述过程。

Floyd 算法可以是一个增量的过程，虽然第一维一般都是从 1枚举到 k但是这个枚举的顺序并不影响最后的结果。

所以如果可以预处理出对于每个点 y，只剩 y 没有在 Floyd 的第一维枚举到的矩阵，这个矩阵的值就是不经过 y 点的全源最短路。

所以使用分治，每一次把点集拆成两半，先用前一半的点在 Floyd 算法中滚，再递归后一半点。

然后回溯，用后一半的点在 Floyd 算法里滚，递归前一半的点。这样每个只有一个点的状态得到的就是只有这个点没有在 Floyd 算法里滚的矩阵。

时间复杂度为 O(n^​3​​logn)。

吐槽：在写这个题以前，cdq分治只写过三维偏序模板题，整体二分的题写的很少，以后要应该多写一些

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <string>

#include <stack>

#include <vector>

#include <map>

#include <queue>

#include <algorithm>

#include <utility>

using namespace std;

typedef long long LL;

const int N=;

const int INF=0x3f3f3f3f;

int dp[][N][N],n,mp[N][N];

LL ret;

void cpydp(int dep){

  for(int i=;i<=n;++i)

    for(int j=;j<=n;++j)

      dp[dep][i][j]=dp[dep-][i][j];

}

void update(int dep,int l,int r){

  for(int k=l;k<=r;++k)

    for(int i=;i<=n;++i)

      for(int j=;j<=n;++j)

        if(dp[dep][i][j]>dp[dep][i][k]+dp[dep][k][j])

           dp[dep][i][j]=dp[dep][i][k]+dp[dep][k][j];

}

void cdq(int dep,int l,int r){

  if(l==r){

    for(int i=;i<=n;++i)

      for(int j=;j<=n;++j){

        if(i==l||j==l)continue;

        if(dp[dep][i][j]==INF)dp[dep][i][j]=-;

        ret+=1ll*dp[dep][i][j];

      }

    return;

  }

  int m=l+r>>;

  cpydp(dep+),update(dep+,m+,r);

  cdq(dep+,l,m);

  cpydp(dep+),update(dep+,l,m);

  cdq(dep+,m+,r);

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;++i)

      for(int j=;j<=n;++j){

        scanf("%d",&dp[][i][j]);

        if(dp[][i][j]==-)dp[][i][j]=INF;

      }

    cdq(,,n);

    cout<<ret<<endl;

    return ;

}

相关文章