Cptraser/ 十月 27, 2018/ 2018.10/ 0 comments

浅谈倍增Floyd

Floyd

Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

考虑这样一道题:求(i,j)经过边数为k的最短路径。
倍增,记f(k,i,j)表示从i出发,走了2^k条边,到j的最短路径。
因为Floyd是传递闭包算法,故可以倍增DP

BZOJ4773负环

倍增Floyd,然后从高位到低位拆分二进制统计答案。
不停更新最短路径图。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int N,M,F[20][305][305],G[305][305],t[305][305],Ans;
int main()
{
    scanf("%d%d",&N,&M);
    memset(F,63,sizeof F),memset(t,63,sizeof t);
    for(int i=1,x,y,c;i<=M;i++){
        scanf("%d%d%d",&x,&y,&c);
        F[0][x][y]=min(F[0][x][y],c);
    }
    for(int i=1;i<=N;i++)F[0][i][i]=t[i][i]=0;
    for(int p=1;(1<<p)<=N;p++)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++)
                for(int k=1;k<=N;k++){
                    F[p][i][j]=min(F[p][i][j],F[p-1][i][k]+F[p-1][k][j]);
                }
    for(int p=17,opt;~p;p--){
        if(1<<p>N)continue;
        memset(G,63,sizeof G),opt=0;
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++)
                for(int k=1;k<=N;k++){
                    G[i][j]=min(G[i][j],t[i][k]+F[p][k][j]);
                }
        for(int i=1;i<=N;i++)if(G[i][i]<0){opt=1;break;}
        if(!opt){
            Ans+=1<<p;
            for(int i=1;i<=N;i++)
                for(int j=1;j<=N;j++)t[i][j]=G[i][j];
        }
    }
    printf("%d\n",Ans>N?0:Ans+1);
}

类似的题目:BZOJ2306Solution

几道尴尬的权限题:
BZOJ1706
BZOJ2165

Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*