本文主要是介绍AcWing 345. 牛站(Floyd变形+快速幂矩阵乘法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
345. 牛站 - AcWing题库
大致题意:从起点到终点,恰好经过N条边的路径数量
定义 g[i][j] 为从i点到j点经过a+b条边的路径数量
假定b[][]为经过a条边的路径数组,c[][]为经过b条边的路径数组
有![g[i][j]=min(g[i][j],b[i][k]+c[k][j])](https://latex.csdn.net/eq?g%5Bi%5D%5Bj%5D%3Dmin%28g%5Bi%5D%5Bj%5D%2Cb%5Bi%5D%5Bk%5D+c%5Bk%5D%5Bj%5D%29)
经过计算后得到的a[][]即为经过a+b条边的路径数组
void floyd(int a[][N],int b[][N],int c[][N])
{static int temp[N][N];//temp数组作为b数组和c组数相乘的结果memset(temp,0x3f,sizeof temp);for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)temp[i][j]=min(temp[i][j],b[i][k]+c[k][j]);memcpy(a,temp,sizeof temp); //复制得到结果
}
最初状态的g[][]即为经过一条边的路径数组
借用快速幂的思想,如果我们想要得到恰好经过K条边的路径数组,如果K为奇数,我们将g[][]与结果数组res[][]计算,如果K为偶数,我们将g[][]与g[][]计算,g[][]的路径长度翻倍,来压缩计算的次数
void qmi()//快速幂套floyd
{memset(res,0x3f,sizeof res);for(int i=1;i<=n;i++) res[i][i]=0;while(K){if(K&1) floyd(res,res,g);//更新答案数组,即res=res*gfloyd(g,g,g);//将g数组倍增,即g=g*gK>>=1;}
}
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>using namespace std;const int N=1010;int K,n,m,S,E;int g[N][N];//开始为只经过一条边的数组
int res[N][N];//答案数组void floyd(int a[][N],int b[][N],int c[][N])
{static int temp[N][N];//temp数组作为b数组和c组数相乘的结果memset(temp,0x3f,sizeof temp);for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)temp[i][j]=min(temp[i][j],b[i][k]+c[k][j]);memcpy(a,temp,sizeof temp); //复制得到结果
}void qmi()//快速幂套floyd
{memset(res,0x3f,sizeof res);for(int i=1;i<=n;i++) res[i][i]=0;while(K){if(K&1) floyd(res,res,g);//更新答案数组,即res=res*gfloyd(g,g,g);//将g数组倍增,即g=g*gK>>=1;}
}int main()
{cin>>K>>m>>S>>E;map<int,int> id;memset(g,0x3f,sizeof g);//因为g数组必须走过一条边,所以g[i][i]不初始化为0,除非i->i之间有边id[S]=++n,id[E]=++n;S=id[S],E=id[E];//离散化过程,因为题目中给的编号并不是从1开始而是随机的;for(int i=1;i<=m;i++){int a,b,c;cin>>c>>a>>b;if(!id.count(a)) id[a]=++n;if(!id.count(b)) id[b]=++n;a=id[a],b=id[b];g[a][b]=g[b][a]=min(g[a][b],c);}qmi();printf("%d",res[S][E]);//输出答案return 0;
}
这篇关于AcWing 345. 牛站(Floyd变形+快速幂矩阵乘法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!