本人水平有限, 题解不到为处, 请多多谅解
本蒟蒻谢谢大家观看
floyd 算法:
设 D[k,i,j]表示 "经过若干个编号不超过 k 的节点" 从 i 到 j 的最短路径长度
D[k,i,j]=min(D[k-1,i,j],D[k-1,i,k]+D[k-1,k,j]);
初始为 D[0,i,j]=A[i,j];A 为邻接矩阵
设有向图 G=(V,E),V 为点集, E 为边集,(x,y)表示一条从 x 到 y 的有向图, 其边权 (或称长度) 为 W(x,y). 设 n=|V|,m=|E|, 邻接矩阵 A 是一个 n*n 的矩阵.
A 的定义如下:
A[i,j]={ 0 i=j
w(i,j) (i,j)属于 E
+∞ (i,j)不属于 E
}
所以 k 为阶段, 所以必须置于最外层循环中
省略 k 这一维之后的 DP
D[i,j]=min(D[i,k]+D[k,j]);
最终 D[i,j]为 i 到 j 的最短路径长度
模板如下:
- code:
- #include<bits/stdc++.h>
- #pragma GCC optimize(3)
- using namespace std;
- int n,m;
- int f[310][310];
- inline int read(){
- int x=0,f=1;char ch=getchar();
- while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
- while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
- return x*f;
- }
- inline void write(int x)
- {
- if(x<0)x=-x,putchar('-');
- if(x>9)write(x/10);
- putchar(x%10+'0');
- }
- int main()
- {
- memset(f,0x3f,sizeof(f));// 初始距离最大
- for(int i=1;i<=n;i++)f[i][i]=0;// 自己到自己的距离为 0
- n=read(),m=read();
- for(int i=1,x,y,z;i<=m;i++){
- x=read(),y=read(),z=read();
- f[x][y]=min(f[x][y],z);// 建邻接矩阵
- }
- for(int k=1;k<=n;k++){
- for(int i=1;i<=n;i++){
- for(int j=1;j<=n;j++){
- f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
- }
- }
- }
- return 0;
- }
应用:
传递闭包
- code:
- #include<bits/stdc++.h>
- #pragma GCC optimize(3)
- using namespace std;
- int n,m;
- bool f[310][310];
- inline int read(){
- int x=0,f=1;char ch=getchar();
- while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
- while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
- return x*f;
- }
- inline void write(int x)
- {
- if(x<0)x=-x,putchar('-');
- if(x>9)write(x/10);
- putchar(x%10+'0');
- }
- int main()
- {
- for(int i=1;i<=n;i++)f[i][i]=1;
- n=read(),m=read();
- for(int i=1,x,y,z;i<=m;i++){
- x=read(),y=read(),z=read();
- f[x][y]=f[y][x]=1;
- }
- for(int k=1;k<=n;k++){
- for(int i=1;i<=n;i++){
- for(int j=1;j<=n;j++){
- f[i][j]|=f[i][k]&f[k][j];
- }
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3266320.html