中国十大知名网站建设,为什么重装电脑没有wordpress,中职示范校建设验收网站,国内景观设计公司前十名目录
一.Floyd算法介绍
二.算法实现
一.邻接矩阵介绍
二.过程简述
三.Floyd核心代码 三.例题分析
一.B3647 【模板】Floyd. 二.P2835 刻录光盘 四.Floyd算法的优缺点 一.Floyd算法介绍 Floyd算法又称为插点法#xff0c;是一种利用动态规划的思想寻找给定的加权图中多源…目录
一.Floyd算法介绍
二.算法实现
一.邻接矩阵介绍
二.过程简述
三.Floyd核心代码 三.例题分析
一.B3647 【模板】Floyd. 二.P2835 刻录光盘 四.Floyd算法的优缺点 一.Floyd算法介绍 Floyd算法又称为插点法是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德。 核心思路通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 算法过程从任意一条单边路径开始。左右两点之间的距离是边的权如果两点之间没有边相连则权为无穷大。 对于每一对顶点u和v看是否存在一个顶点w使得从u到w再到v比已知的路径更短如果更短则更新它。 上述概念来源于百度百科 Floyd算法可以用来求图结构中任意两点的最短路径即“多源最短路径”问题。
二.算法实现
对于实现Floyd算法我们通常需要通过邻接矩阵二维数组的实现。
一.邻接矩阵介绍 邻接矩阵就是利用二维矩阵表示图中各顶点之间的关系对于有n个顶点的图来说用n阶方阵来表示该图其中矩阵元素表示从顶点到之间的边的大小表示边的权值。如果顶点到没有边则可以将设置为0或者。 例如在该图中任意一点ij代表着从i和j边的权特定情景可能是距离消费通常我们将所以点初始化为无穷大自己指向自己的点为0。 二.过程简述 如果要让任意两点之间(假设是a到b)的路程变短智能引入第三个点(假设为k)并通过这个点k进行中转即a-k-b,才可能缩短为原来从顶点a到顶点b的路程。有时候可能不止一个中转点而是经过两个或者更多的点进行中转会更短。比如上图中的4号和3号之间的路程本来是a[4][3]12,如果通过1号中转4-1-3路程将缩短为e[4][1]e[1][3]5611。如果同时通过1号和2号中转的话从4号到3号的路程会进一步缩短为e[4]e[1][2]e[2][3]52310。通过以上分析我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。 通过以上过程的分析我们最终可以得到一个邻接矩阵。 三.Floyd核心代码
Floyd算法的核心代码非常简洁只有短短5行。
for (int k 1; k n; k) { //注意中转点在循环的最外层for (int i 1; i n; i) {for (int j 1; j n; j) {if (e[i][j] e[i][k] e[k][j]) //如果当前小于重组后e[i][j] e[i][k] e[k][j]; //将当前值替代}}
} 三.例题分析
一.B3647 【模板】Floyd.
https://www.luogu.com.cn/problem/B3647
题目描述
给出一张由 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。
数据中可能存在重边。 本题是Floyd算法的模版题我们只要照着刚才的过程模拟写就可以。
#includebits/stdc.husing namespace std;
#define MAX 5000 //宏定义一个很大的数代表无穷大
int a[MAX][MAX]; //邻接矩阵int main()
{int n,m;cinnm;for(int i1;in;i) //初始化邻接矩阵{for(int j1;jn;j){if(ij)a[i][j]0; //对角线上的点自己指向自己赋值为0elsea[i][j]MAX;//没有边联通的点赋值为无穷大}}for(int i1;im;i){int u,v,w;cinuvw;a[u][v]min(a[u][v],w); //无向边所以关于对角线对称a[v][u]min(a[v][u],w); //因为可能有重边所以取最小}for(int k1;kn;k) //Floyd算法核心代码段{for(int i1;in;i){for(int j1;jn;j){a[i][j]min(a[i][k]a[k][j],min(a[i][j],a[j][i])); //找到最短进行赋值}}}for(int i1;in;i){for(int j1;jn;j){couta[i][j] ; //遍历输出邻接矩阵}coutendl;}return 0;
} 二.P2835 刻录光盘
https://www.luogu.com.cn/problem/P2835
题目描述
在JSOI2005夏令营快要结束的时候很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家以便大家回去后继续学习。组委会觉得这个主意不错可是组委会一时没有足够的空光盘没法保证每个人都能拿到刻录上资料的光盘又来不及去买了怎么办呢
组委会把这个难题交给了LHCLHC分析了一下所有营员的地域关系发现有些营员是一个城市的其实他们只需要一张就可以了因为一个人拿到光盘后其他人可以带着U盘之类的东西去拷贝啊
可是LHC调查后发现由于种种原因有些营员并不是那么的合作他们愿意某一些人到他那儿拷贝资料当然也可能不愿意让另外一些人到他那儿拷贝资料这与我们JSOI宣扬的团队合作精神格格不入
现在假设总共有N个营员2N200每个营员的编号为1~N。LHC给每个人发了一张调查表让每个营员填上自己愿意让哪些人到他那儿拷贝资料。当然如果A愿意把资料拷贝给B而B又愿意把资料拷贝给C则一旦A获得了资料则BC都会获得资料。
现在请你编写一个程序根据回收上来的调查表帮助LHC计算出组委会至少要刻录多少张光盘才能保证所有营员回去后都能得到夏令营资料
输入格式
先是一个数N接下来的N行分别表示各个营员愿意把自己获得的资料拷贝给其他哪些营员。即输入数据的第i1行表示第i个营员愿意把资料拷贝给那些营员的编号以一个0结束。如果一个营员不愿意拷贝资料给任何人则相应的行只有1个0一行中的若干数之间用一个空格隔开。
输出格式
一个正整数表示最少要刻录的光盘数。
输入输出样例
输入 #1复制
5
2 3 4 0
4 5 0
0
0
1 0
输出 #1复制
1
这道题我是通过并查集和Floyd联合起来使用的通过题意我们知道这里的关系图是单向的我们只需要使用Floyd算法的将原意共享的人通过邻接矩阵表示出来然后通过并查集查找出分为多少个集体统计集体个数就可以了。 #includebits/stdc.h
using namespace std;
#define MAX 205
bool vis[MAX][MAX]; //邻接矩阵
int pre[MAX]; //前驱数组
int n,ans0;void solve()
{for(int i1;in;i){int x;while(1){cinx;if(x!0) //果然x值不为0说明他愿意拷贝给xvis[i][x]1; //将代表i原意拷贝给x的点赋为1elsebreak;}}for(int k1;kn;k) //Floyd算法核心代码段{for(int i1;in;i){for(int j1;jn;j){if(vis[i][k]vis[k][j]) //如果i原意给kk愿意给jvis[i][j]1; //那么相当于i愿意给j}}}
}
int main()
{cinn;for(int i1;in;i)pre[i]i; //初始化前驱数组solve();for(int i1;in;i){for(int j1;jn;j){if(vis[i][j]) //如果邻接矩阵中的点不为0说明i原意给j拷贝pre[j]pre[i]; //将j的前驱改为i的前驱}}for(int i1;in;i)if(pre[i]i) //如果找到一个小集体即前驱是自己ans; //光盘数加一coutansendl;return 0;
} 四.Floyd算法的优缺点
优点Floyd算法容易理解代码简洁可以处理图结构中任意两点的最短路径。Floyd算法可以处理带有负权边边的值为负数的图。
缺点Floyd算法的时间复杂度是O(N^3)时间复杂度很高。并且不能处理带有“负权回路”的图。 今天的博客就到这里了~QVQ~
