并不对劲的[USACO07NOV，洛谷p2886]Cow Relays

题意就是给一张无向有边权的图、起点、终点，求起点到终点经过n条边的最短路。n<=10^6，点的编号<=10^3，边数<=10^2。

这个边数让人不由自主地想到了floyd，然后发现floyd每次相当于加入了一个点（注意，这里的“一次”也是O(点数^3)的，但是在这一次floyd的过程中不会更新结果。）也就是说，第一次floyd求出来了两点之间只走一条边的最短路，第二次求出来了两点之间只走两条边的最短路……，第n次求出来了只走n条边的最短路。这时候就会发现，n遍不在过程中更新答案的floyd后，答案就出来了。

好不容易推到了这一步，发现了n<=10^6的数据范围，想必心中是有些崩溃的。但是邻接矩阵是什么？是矩阵！这样就可以思考用矩阵快速幂的方法。发现floyd的转移时c[i][j] = min { dis[i][k] + dis[k][j] | i,k,j为图中点的编号}，和矩阵快速幂的转移有点像，而且转移时也是上一步求出的答案对于最初的邻接矩阵作运算。这时就可以考虑用一些不对劲的方法改造矩阵乘法。

将矩阵快速幂中的乘法改成上面那样的转移方法，就会发现只要求出邻接矩阵^n就好了。

这样就完了？当然不是。

题目中，点的编号<=10^3，直接floyd肯定会时间超限。注意到边数<=10^2，而每条边顶多连两个与之前不同的点，那么出现的不同的点顶多有200个。将点进行离散化就解决了。

还有一些细节，编的时候都能想得到，在这就不多说了。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<iomanip>

#include<cstdlib>

using namespace std;

typedef struct node{

    int mat[][];

}Matrix;

Matrix rd,dis;

int n,t,s,e,siz,mc[];

int read(){

    int x=,f=;

    char ch=getchar();

    while(isdigit(ch)== && ch!='-')ch=getchar();

    if(ch=='-')f=-;

    while(isdigit(ch))x=x*+ch-'',ch=getchar();

    return x*f;

}

Matrix mul(Matrix a,Matrix b){

    Matrix c;

    memset(c.mat,0x3f,sizeof(c.mat));

    for(int k=;k<=siz;k++){

        for(int i=;i<=siz;i++){

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

                c.mat[i][j]=min(c.mat[i][j],a.mat[i][k]+b.mat[k][j]);

            }

        }

    }

    return c;

}

void pow(int tim){

    while(tim)

    {

        if(tim&)

            rd=mul(rd,dis);

        dis=mul(dis,dis);

        tim>>=;

    }

}

int main(){

    //freopen(".in","r",stdin);

    //freopen(".out","w",stdout);

    n=read(),t=read(),s=read(),e=read();

    memset(rd.mat,0x3f,sizeof(rd.mat));

    memset(dis.mat,0x3f,sizeof(dis.mat));

    memset(mc,-,sizeof(mc));

    for(int i=;i<=t;i++){

        int w=read(),u=read(),v=read();

        if(mc[u]==-)mc[u]=++siz;

        if(mc[v]==-)mc[v]=++siz;

        u=mc[u],v=mc[v];

        dis.mat[v][u]=min(dis.mat[u][v],w);

        dis.mat[u][v]=min(dis.mat[u][v],w);

    }

    for(int i=;i<=siz;i++){

        rd.mat[i][i]=;

    }

    pow(n);

    cout<<rd.mat[mc[s]][mc[e]];

    return ;

}

并不对劲的矩阵快速幂

巴特西

并不对劲的[USACO07NOV，洛谷p2886]Cow Relays

最新文章

热门文章