Floyd 弗洛伊德算法(最短路径、传递闭包)

文章目录Floyd 弗洛伊德算法(最短路径、传递闭包)1.Floyd求多源最短路1.1公式1.2循环结构重点1.3初始化2.Floyd 传递闭包例题解题过程实现代码Floyd 弗洛伊德算法(最短路径、传递闭包)存储方式:邻接矩阵存图用途1:任意两个点的最短距离多源最短路用途2求传递闭包判断i点是否可以到达j点核心枚举中转点mid尝试借助mid更新i到j的距离1.Floyd求多源最短路状态定义dis[i][j]表示点i到点j的最短距离1.1公式d i s [ i ] [ j ] min ⁡ ( d i s [ i ] [ j ] , d i s [ i ] [ m i d ] d i s [ m i d ] [ j ] ) dis[i][j]\min(dis[i][j],dis[i][mid]dis[mid][j])dis[i][j]min(dis[i][j],dis[i][mid]dis[mid][j])1.2循环结构重点中转点mid 必须在最外层for(int mid1;midn;mid) for(int i1;in;i) for(int j1;jn;j) dis[i][j]min(dis[i][j],dis[i][mid]dis[mid][j]);1.3初始化dis[i][i]0点到自身距离为 0没有直接边的两点初始化为无穷大INFdis[i][j]wi,j 之间有边则赋值边权 w复杂度On3适合顶点数n较小的图n一般不超过3002.Floyd 传递闭包传递闭包概念维护布尔矩阵f[i][j]f[i][j]truei 可以到达 jf[i][j]falsei 不能到达 j逻辑如果 i 能到 midmid 能到 j那么 i 就可以到达 j。//Floyd传递闭包模板 for(ll mid0;mid9;mid) //中转点mid必须放在最外层 { for(ll i0;i9;i) { for(ll j0;j9;j) { if(f[i][mid]f[mid][j]) { f[i][j]true; } } } }为什么 mid 必须放在最外层要先把以mid作为中转点的全部可达关系更新完毕再切换下一个中转点。如果把i或j放最外层传递关系更新不完全会漏掉路径得到错误结果初始化f[i][i]true每个点可以到达自己。例题涉及:Floyd 传递闭包 高精度乘法**不需要 DFS[P1037 NOIP 2002 普及组] 产生数 - 洛谷✨✨解题过程数据说明在题目中n的范围直接到1e64非常的大 肯定就用字符串存关于题目n2342–53–6那么对于整个过程中2可以变成2 和53可以变成本身3和64只有变 本身 这一个选择4整个过程中只有每个变化相乘 4种变化但是这个过程中也涉及到————高精度乘法(高精度乘低精度)高精度vector低位存在数组前面输出的时候再反转就好vectorllmul(vectorlla,ll x) { vectorllres; ll t0; for(ll num:a) { tnum*x;//高精度*低精度 res.push_back(t%10); t/10; } while(t!0) { res.push_back(t%10); t/10; } return res; }还有一个特殊情况假如说2–4;4–6 ;那就可以得到一个2–6的传递过程————可以用Floyd传递闭包三重循环mid必须放在最外层//Floyd传递闭包 for(ll mid0;mid9;mid) { for(ll i0;i9;i) { for(ll j0;j9;j) { if(f[i][mid]f[mid][j]) { f[i][j]true; } } } }实现代码#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; string s; ll k; bool f[10][10]; vectorllmul(vectorlla,ll x) { vectorllres; ll t0; for(ll num:a) { tnum*x; res.push_back(t%10); t/10; } while(t!0) { res.push_back(t%10); t/10; } return res; } int main() { IOS cinsk; for(ll i0;i9;i) { f[i][i]true; } for(ll i1;ik;i) { ll x,y; cinxy; f[x][y]true; } //Floyd传递闭包 for(ll mid0;mid9;mid) { for(ll i0;i9;i) { for(ll j0;j9;j) { if(f[i][mid]f[mid][j]) { f[i][j]true; } } } } ll cnt[10]{0}; //统计多少种变化 for(ll i0;i9;i) { for(ll j0;j9;j) { if(f[i][j]) { cnt[i]; } } } vectorllans; ans.push_back(1); for(char c:s) { ll dc-0; ansmul(ans,cnt[d]); } reverse(ans.begin(),ans.end()); for(ll x:ans) { coutx; } coutendl; // coutfixedsetprecision(x) ; return 0; }} } } vectorllans; ans.push_back(1); for(char c:s) { ll dc-0; ansmul(ans,cnt[d]); } reverse(ans.begin(),ans.end()); for(ll x:ans) { coutx; } coutendl;// coutfixedsetprecision(x) ;return 0;}