首页 > 代码库 > BZOJ1706: [usaco2007 Nov]relays 奶牛接力跑
BZOJ1706: [usaco2007 Nov]relays 奶牛接力跑
一个编号在1000内的m条边的图,求从s到t恰好经过D条路径的最短路。
一开始什么想法都没有。。之前写过分层图套进去也怪怪的。。毕竟D<=10^6
苦思冥想睡了一觉后,还是没思路,查查题解,打开了新世界的大门
没有重边,提示我们构造邻接矩阵,最短路可以用floyd求出,但怎么用Floyd来“限边”???
在原邻接矩阵,即“走一步最短路”中,以原邻接矩阵为路径,floyd走一次,就变成“走两步最短路”
在新矩阵中,即“走两步最短路”中,以新矩阵为路径,floyd走一次,就变成“走四步最短路”
等等,这怎么有种矩阵快速幂的感觉?没错,把矩阵快速幂的乘法和加法改成加法和min,就可以做了。
当然,1000*1000来快速幂有点慢了,先离散化吧
有个小问题,不知道ans矩阵怎么初始化,所以特判了一波。。。。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<cstring> 6 //#include<iostream> 7 using namespace std; 8 9 int D,n,m,s,t; 10 #define maxn 1011 11 int id[maxn]; 12 #define maxm 211 13 const int inf=0x3f3f3f3f; 14 struct Matrix 15 { 16 int a[maxm][maxm]; 17 void clear(int n) 18 { 19 for (int i=1;i<=n;i++) 20 for (int j=1;j<=n;j++) 21 a[i][j]=inf; 22 } 23 Matrix operator * (const Matrix &b) 24 { 25 Matrix ans; 26 ans.clear(n); 27 for (int k=1;k<=n;k++) 28 for (int i=1;i<=n;i++) 29 for (int j=1;j<=n;j++) 30 if (ans.a[i][j]>a[i][k]+b.a[k][j]) 31 ans.a[i][j]=a[i][k]+b.a[k][j]; 32 return ans; 33 } 34 }tmp,ans; 35 int x,y,v; 36 int getid(int x) 37 { 38 if (!id[x]) id[x]=++n; 39 return id[x]; 40 } 41 int main() 42 { 43 scanf("%d%d%d%d",&D,&m,&s,&t); 44 memset(id,0,sizeof(id)); 45 tmp.clear(201); 46 n=0; 47 for (int i=1;i<=m;i++) 48 { 49 scanf("%d",&v); 50 scanf("%d%d",&x,&y); 51 x=getid(x),y=getid(y); 52 tmp.a[x][y]=tmp.a[y][x]=v; 53 } 54 bool flag=0; 55 while (D) 56 { 57 if (D&1) 58 { 59 if (flag) ans=ans*tmp; 60 else 61 { 62 flag=1; 63 memcpy(ans.a,tmp.a,sizeof(ans.a)); 64 } 65 } 66 tmp=tmp*tmp; 67 D>>=1; 68 } 69 printf("%d\n",ans.a[getid(s)][getid(t)]); 70 return 0; 71 }
BZOJ1706: [usaco2007 Nov]relays 奶牛接力跑
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。