php 微网站开发可以在线制作网页的网站

php 微网站开发,可以在线制作网页的网站,云服务器是什么,显示网站建设精美页面多源最短路 多源最短路#xff1a;即图中每对顶点间的最短路径。floyd 算法本质是动态规划#xff0c;⽤来求任意两个结点之间的最短路#xff0c;也称插点法。通过不断在两点之间加 ⼊新的点#xff0c;来更新最短路。 适⽤于任何图#xff0c;不管有向⽆向#xff0c;…多源最短路多源最短路即图中每对顶点间的最短路径。floyd 算法本质是动态规划⽤来求任意两个结点之间的最短路也称插点法。通过不断在两点之间加 ⼊新的点来更新最短路。适⽤于任何图不管有向⽆向边权正负但是最短路必须存在也就是不存在负环。1. 状态表⽰f[k][i][j]表⽰仅仅经过[1, k]这些点结点i⾛到结点j的最短路径 的⻓度。2. 状态转移⽅程•第⼀种情况不选新来的点f[k][i][j] f[k - 1][i][j]•第⼆种情况选择新来的点f[k][i][j] f[k - 1][i][k] f[k - 1][k][j]3. 空间优化只会⽤到上⼀层的状态因此可以优化到第⼀维。4. 初始化•f[i][i] 0•f[i][j]为初始状态下i到j的距离如果没有边则为⽆穷。5. 填表顺序•⼀定要先枚举k再枚举i和j。因为我们填表的时候需要依赖的是k - 1层的状态因此k必须先枚举。1【模板】floyd题⽬来源 洛⾕题⽬链接B3647 【模板】Floyd难度系数 ★题目描述给出一张由 n 个点 m 条边组成的无向图。求出所有点对 (i,j) 之间的最短路径。输入格式第一行为两个整数 n,m分别代表点的个数和边的条数。接下来 m 行每行三个整数 u,v,w代表 u,v 之间存在一条边权为 w 的边。输出格式输出 n 行每行 n 个整数。第 i 行的第 j 个整数代表从 i 到 j 的最短路径。输入输出样例输入 #1复制4 4 1 2 1 2 3 1 3 4 1 4 1 1输出 #1复制0 1 2 1 1 0 1 2 2 1 0 1 1 2 1 0说明/提示对于 100% 的数据n≤100m≤4500任意一条边的权值 w 是正整数且 1⩽w⩽1000。数据中可能存在重边。【解法】模板题。【参考代码】#include iostream #include cstring using namespace std; const int N 110; // 最多110个点适配题目数据范围 int n, m; // n点数m边数 int f[N][N]; // 邻接矩阵f[i][j] i到j的最短距离 int main() { // 第一步输入点数和边数 cin n m; // 第二步初始化邻接矩阵 memset(f, 0x3f, sizeof f); // 所有距离初始化为“无穷大”0x3f≈10亿 for (int i 1; i n; i) { f[i][i] 0; // 自己到自己的距离为0 } // 第三步输入m条无向边更新邻接矩阵 for (int i 1; i m; i) { int u, v, w; cin u v w; // 无向边u↔v取最小边权防止重边 f[u][v] f[v][u] min(f[u][v], w); } // 第四步Floyd核心——三层循环更新所有点对的最短距离 // k中间点枚举所有可能的中转点 for (int k 1; k n; k) { // i起点 for (int i 1; i n; i) { // j终点 for (int j 1; j n; j) { // 状态转移i→j的最短距离 min(原距离, i→k k→j) f[i][j] min(f[i][j], f[i][k] f[k][j]); } } } // 第五步输出结果n行n列 for (int i 1; i n; i) { for (int j 1; j n; j) { cout f[i][j] ; } cout endl; // 每行结束换行 } return 0; }2Clear And Present Danger题⽬来源 洛⾕题⽬链接P2910 [USACO08OPEN] Clear And Present Danger S难度系数 ★★题目描述农夫约翰正驾驶一条小艇在牛勒比海上航行。海上有 N(1≤N≤100) 个岛屿用 1 到 N 编号。约翰从 1 号小岛出发最后到达 N 号小岛。一张藏宝图上说如果他的路程上经过的小岛依次出现了 A1​,A2​,…,AM​(2≤M≤10000) 这样的序列不一定相邻那他最终就能找到古老的宝藏。但是由于牛勒比海有海盗出没约翰知道任意两个岛屿之间的航线上海盗出没的概率他用一个危险指数 Di,j​(0≤Di,j​≤100000) 来描述。他希望他的寻宝活动经过的航线危险指数之和最小。那么在找到宝藏的前提下这个最小的危险指数是多少呢输入格式第一行两个用空格隔开的正整数 N 和 M。第二到第 M1 行第 i1 行用一个整数 Ai​ 表示 FJ 必须经过的第 i 个岛屿。保证 A1​1,AM​N。第 M2 到第 NM1 行第 iM1 行包含 N 个用空格隔开的非负整数分别表示 i 号小岛到第 1…N 号小岛的航线各自的危险指数。保证第 i 个数是 0。输出格式第一行FJ 在找到宝藏的前提下经过的航线的危险指数之和的最小值。显示翻译题意翻译输入输出样例输入 #1复制3 4 1 2 1 3 0 5 1 5 0 2 1 2 0输出 #1复制7说明/提示样例说明 #1这组数据中有三个岛屿藏宝图要求 FJ 按顺序经过四个岛屿1 号岛屿、2 号岛屿、回到 1 号岛屿、最后到 3 号岛屿。每条航线的危险指数也给出了航路(1,2),(2,3),(3,1) 和它们的反向路径的危险指数分别是 5,2,1。FJ 可以通过依次经过 1,3,2,3,1,3 号岛屿以 7 的最小总危险指数获得宝藏。这条道路满足了奶牛地图的要求 (1,2,1,3)。我们避开了 1 号和 2 号岛屿之间的航线因为它的危险指数太大了。注意测试数据中 a 到 b 的危险指数不一定等于 b 到 a 的危险指数Translated by LJC00125【解法】⽤ floyd 算法求出任意两点的最短路即可。【参考代码】#includeiostream #includecstring using namespace std; typedef long long LL; // 防止总距离溢出比如多次累加大数 const int N110; // 最多110个点Floyd算法n³复杂度适配 const int M1e410; // 最多1e4个访问点 int n, m; // n点数m访问序列长度 int a[M]; // 访问序列a[1]~a[m]是依次要走的点 int f[N][N]; // 邻接矩阵f[i][j] i到j的最短距离 int main() { // 第一步输入点数n和访问序列长度m cin n m; // 第二步输入访问序列m个点的编号 for(int i1; im; i) { cin a[i]; } // 第三步输入初始邻接矩阵n行n列f[i][j]是i到j的初始距离 for(int i1; in; i) { for(int j1; jn; j) { cin f[i][j]; } } // 第四步Floyd算法预处理所有点对的最短路径 // k中转点i起点j终点 for(int k1; kn; k) { for(int i1; in; i) { for(int j1; jn; j) { // 状态转移i→j的最短距离 min(原距离, i→k k→j) f[i][j] min(f[i][j], f[i][k] f[k][j]); } } } // 第五步计算访问序列的总最短距离 LL ret 0; // 用LL防止溢出 for(int i2; im; i) { // 累加a[i-1]到a[i]的最短距离 ret f[a[i-1]][a[i]]; } // 第六步输出总距离 cout ret endl; return 0; }3灾后重建题⽬来源 洛⾕题⽬链接P1119 灾后重建难度系数 ★★★题目背景B 地区在地震过后所有村庄都造成了一定的损毁而这场地震却没对公路造成什么影响。但是在村庄重建好之前所有与未重建完成的村庄的公路均无法通车。换句话说只有连接着两个重建完成的村庄的公路才能通车只能到达重建完成的村庄。题目描述给出 B 地区的村庄数 N村庄编号从 0 到 N−1和所有 M 条公路的长度公路是双向的。并给出第 i 个村庄重建完成的时间 ti​你可以认为是同时开始重建并在第 ti​ 天重建完成并且在当天即可通车。若 ti​ 为 0 则说明地震未对此地区造成损坏一开始就可以通车。之后有 Q 个询问 (x,y,t)对于每个询问你要回答在第 t 天从村庄 x 到村庄 y 的最短路径长度为多少。如果无法找到从 x 村庄到 y 村庄的路径经过若干个已重建完成的村庄或者村庄 x 或村庄 y 在第 t 天仍未重建完成则需要输出 −1。输入格式第一行包含两个正整数 N,M表示了村庄的数目与公路的数量。第二行包含 N 个非负整数 t0​,t1​,⋯,tN−1​表示了每个村庄重建完成的时间数据保证了 t0​≤t1​≤⋯≤tN−1​。接下来 M 行每行 3 个非负整数 i,j,ww 不超过 10000表示了有一条连接村庄 i 与村庄 j 的道路长度为 w保证 ij且对于任意一对村庄只会存在一条道路。接下来一行也就是 M3 行包含一个正整数 Q表示 Q 个询问。接下来 Q 行每行 3 个非负整数 x,y,t询问在第 t 天从村庄 x 到村庄 y 的最短路径长度为多少数据保证了 t 是不下降的。输出格式共 Q 行对每一个询问 (x,y,t) 输出对应的答案即在第 t 天从村庄 x 到村庄 y 的最短路径长度为多少。如果在第 t 天无法找到从 x 村庄到 y 村庄的路径经过若干个已重建完成的村庄或者村庄 x 或村庄 y 在第 t 天仍未修复完成则输出 −1。输入输出样例输入 #1复制4 5 1 2 3 4 0 2 1 2 3 1 3 1 2 2 1 4 0 3 5 4 2 0 2 0 1 2 0 1 3 0 1 4输出 #1复制-1 -1 5 4说明/提示对于 30% 的数据有 N≤50对于 30% 的数据有 ti​0其中有 20% 的数据有 ti​0 且 N50对于 50% 的数据有 Q≤100对于 100% 的数据有 1≤N≤2000≤M≤2N×(N−1)​1≤Q≤50000所有输入数据涉及整数均不超过 105。【解法】希望⼤家通过这道题理解 floyd 算法的本质。在 floyd 算法中我们是⼀个点⼀个点加⼊到最短路的更新中那么这道题其实就是限制了我们加点的 时机。当从前往后遍历每次询问的时候直到时间点在询问的时间 t 之前的点都可以加⼊到最短路的 更新中。那么就可以⼀边读取询问⼀边通过时间限制更新最短路。【参考代码】#include iostream #include cstring using namespace std; const int N 210; // 村庄数量上限210 const int INF 0x3f3f3f3f; // 无穷大≈10亿大于最大可能路径和 int n, m; // n村庄数m公路数 int t[N]; // t[i]第i个村庄的重建完成时间 int f[N][N]; // 邻接矩阵f[i][j] i到j的最短路径长度 // Floyd核心函数加入中转点k更新所有i→j的最短路径 void floyd(int k) { for (int i 0; i n; i) { for (int j 0; j n; j) { // 状态转移i→j的最短路径 min(原路径, i→k k→j) f[i][j] min(f[i][j], f[i][k] f[k][j]); } } } int main() { // 第一步输入村庄数和公路数 cin n m; // 第二步输入每个村庄的重建完成时间题目保证t[0]≤t[1]≤…≤t[n-1] for (int i 0; i n; i) { cin t[i]; } // 第三步初始化邻接矩阵 memset(f, 0x3f, sizeof f); // 所有路径初始化为无穷大 for (int i 0; i n; i) { f[i][i] 0; // 自己到自己的路径长度为0 } // 第四步输入公路信息双向边 for (int i 1; i m; i) { int a, b, c; cin a b c; // 双向公路取最小长度题目保证无重边min可省略但保留更通用 f[a][b] f[b][a] min(f[a][b], c); } // 第五步处理查询 int Q; // 查询数量 cin Q; int pos 0; // 记录当前已加入的最后一个中转点利用t递增、查询t不下降的特性 while (Q--) { int x, y, time; // 查询time天x到y的最短路径 cin x y time; // 关键把所有重建完成时间≤time的村庄作为中转点加入Floyd while (pos n t[pos] time) { floyd(pos); // 加入中转点pos更新所有路径 pos; // 下一个待加入的中转点 } // 判定输出条件 // 1. x或y未重建t[x]/t[y] time2. x到y无路径f[x][y]INF→ 输出-1 if (t[x] time || t[y] time || f[x][y] INF) { cout -1 endl; } else { cout f[x][y] endl; } } return 0; }4⽆向图的最⼩环问题题⽬来源 洛⾕题⽬链接P6175 ⽆向图的最⼩环问题难度系数 ★★题目描述给定一张无向图求图中一个至少包含 3 个点的环环上的节点不重复并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中你需要输出最小的环的边权和。若无解输出No solution.。输入格式第一行两个正整数 n,m 表示点数和边数。接下来 m 行每行三个正整数 u,v,d表示节点 u,v 之间有一条长度为 d 的边。输出格式输出边权和最小的环的边权和。若无解输出No solution.。输入输出样例输入 #1复制5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20输出 #1复制61说明/提示样例解释一种可行的方案1−3−5−2−1。对于 20% 的数据n,m≤10。对于 60% 的数据m≤100。对于 100% 的数据1≤n≤1001≤m≤5×1031≤d≤105。无解输出包括句号。【解法】floyd 算法的性质•在计算第k层的时候f[i][j]⾥⾯存储着中转点为[1, k - 1]时的最短路。如果设环⾥的最⼤结点的编号为k与 k 相邻的点为i, j其中i k j k i! j•那么我们在 floyd 算法循环到k的时候这个环的最⼩⻓度为f[i][j] e[i][k] e[j][k]。•环的最⼤编号是任意的因此在所有情况下取最⼩值即可【参考代码】#include iostream #include cstring using namespace std; const int N 110, INF 1e8; int n, m; int e[N][N]; int f[N][N]; int main() { cin n m; // memset(e, 0x3f, sizeof e); // memset(f, 0x3f, sizeof f); for(int i 1; i n; i) for(int j 1; j n; j) f[i][j] e[i][j] INF; for(int i 1; i n; i) e[i][i] f[i][i] 0; for(int i 1; i m; i) { int a, b, c; cin a b c; e[a][b] e[b][a] f[a][b] f[b][a] min(e[a][b], c); } int ret INF; for(int k 1; k n; k) { // 最⼩环 for(int i 1; i k; i) for(int j i 1; j k; j) ret min(ret, f[i][j] e[i][k] e[k][j]); // 最短距离 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]); } if(ret INF) cout No solution. endl; else cout ret endl; return 0; }