《图的最短路径ppt课件》由会员分享，可在线阅读，更多相关《图的最短路径ppt课件（45页珍藏版）》请在金锄头文库上搜索。
1、图的最短路径图的最短路径7 7月月月月1717日日日日3.5图的最短路径图的最短路径【知识点】【知识点】掌握图的传递闭包、最短路的概念。掌握图的传递闭包、最短路的概念。掌握最短路的求解方法，理解掌握最短路的求解方法，理解floyd算法、算法、dijkstra算法的适用范围，最短路算法的算法的适用范围，最短路算法的灵活应用。灵活应用。【知识讲解】【知识讲解】3.5.1图的传递闭包图的传递闭包求解问题：对于图求解问题：对于图G的任意顶点的任意顶点i和和j，是否存在，是否存在一条从一条从i到到j的路径（即的路径（即i和和j是否可达）？是否可达）？（1）对于图对于图G的任意一个顶点的任意一个顶点u，u
2、可达的顶点可达的顶点集合称为集合称为u的传递闭包。在无向图中，的传递闭包。在无向图中，u的传递的传递闭包为和闭包为和u处于同一处于同一连通分量连通分量的点集。有向图中，的点集。有向图中，u的传递闭包为的传递闭包为u可达的顶点集合。可达的顶点集合。1234657123465711110001111000111100011110000000111000011100001110110000101000011010000010000000001000001010000010邻接矩阵邻接矩阵G*G Gi和和j是否有是否有边边相连？相连？i和和j是否有是否有路路相连相连（可达）（可达）？（2 2）求解传递
3、闭包的算法）求解传递闭包的算法）求解传递闭包的算法）求解传递闭包的算法判断结点判断结点判断结点判断结点ii到到到到j j是否有路径，只有两种情况：是否有路径，只有两种情况：是否有路径，只有两种情况：是否有路径，只有两种情况： 结点结点结点结点ii到到到到jj有边，则有路径。有边，则有路径。有边，则有路径。有边，则有路径。ii到到到到jj之间没有边：之间没有边：之间没有边：之间没有边： 如果存在另外的一个结点如果存在另外的一个结点如果存在另外的一个结点如果存在另外的一个结点k k，满足：，满足：，满足：，满足：i i到到到到k k有路径，有路径，有路径，有路径，k k到到到到j j有路径，则有路
4、径，则有路径，则有路径，则i i到到到到j j有路有路有路有路径。否则径。否则径。否则径。否则i i到到到到j j没有路径。没有路径。没有路径。没有路径。则：则：则：则：canij=canij|(canik&cankj)canij=canij|(canik&cankj)ijkijk初始化：初始化：初始化：初始化：canij=true:icanij=true:i到到到到j j有边；有边；有边；有边；canij=false:icanij=false:i到到到到j j无边。无边。无边。无边。canii=truecanii=true；求解过程：求解过程：求解过程：求解过程：for(intk=1;k=n
5、;k+)for(intk=1;k=n;k+)枚举中间点枚举中间点枚举中间点枚举中间点for(inti=1;i=n;i+)for(inti=1;i=n;i+)枚举起点枚举起点枚举起点枚举起点for(intj=1;j=n;j+)for(intj=1;j=n;j+)枚举终点枚举终点枚举终点枚举终点canij=canij|(canik&cankj);canij=canij|(canik&cankj); 引例引例引例引例 ：现在，我们想从城市现在，我们想从城市现在，我们想从城市现在，我们想从城市A A A A到达城市到达城市到达城市到达城市E E E E。怎样走才能使得路径最短，最短路径的长度是多少？怎
6、样走才能使得路径最短，最短路径的长度是多少？怎样走才能使得路径最短，最短路径的长度是多少？怎样走才能使得路径最短，最短路径的长度是多少？ 3.5.2图的最短路径图的最短路径已知各个城市之间的道路情况如下：已知各个城市之间的道路情况如下：已知各个城市之间的道路情况如下：已知各个城市之间的道路情况如下：12345678910115312384385523438A AE E图中两点间的最短距离图中两点间的最短距离两类问题：两类问题：两类问题：两类问题：1 1、图中每对顶点（任意两点）之间的最短路径、图中每对顶点（任意两点）之间的最短路径、图中每对顶点（任意两点）之间的最短路径、图中每对顶点（任意两点
7、）之间的最短路径（弗洛伊德算法：弗洛伊德算法：弗洛伊德算法：弗洛伊德算法：f floyedloyed）。）。）。）。2 2、图中一个顶点到其他顶点的最短路径（单源最、图中一个顶点到其他顶点的最短路径（单源最、图中一个顶点到其他顶点的最短路径（单源最、图中一个顶点到其他顶点的最短路径（单源最短路径）短路径）短路径）短路径）（dijkstradijkstra算法算法算法算法、 Bellman-fordBellman-ford算法、算法、算法、算法、SPFASPFA算法算法算法算法）。）。）。）。3.5.33.5.3计算每一对顶点间的最短路径（计算每一对顶点间的最短路径（计算每一对顶点间的最短路径（
8、计算每一对顶点间的最短路径（floydfloyd算法）算法）算法）算法）（一）求最短距离（一）求最短距离（一）求最短距离（一）求最短距离目标：把图中任意两点目标：把图中任意两点目标：把图中任意两点目标：把图中任意两点i i与与与与j j之间的最短距离都求出来之间的最短距离都求出来之间的最短距离都求出来之间的最短距离都求出来dijdij。原理：任意一个最短路算法都是基于这样一个事实：从任原理：任意一个最短路算法都是基于这样一个事实：从任原理：任意一个最短路算法都是基于这样一个事实：从任原理：任意一个最短路算法都是基于这样一个事实：从任意节点意节点意节点意节点A A到任意节点到任意节点到任意节点到
9、任意节点B B的最短路径不外乎的最短路径不外乎的最短路径不外乎的最短路径不外乎2 2种可能：种可能：种可能：种可能：1 1是直接从是直接从是直接从是直接从A A到到到到B B，2 2是从是从是从是从A A经过若干个节点到经过若干个节点到经过若干个节点到经过若干个节点到B B。if(dik+dkjdij)dij=dik+dkj算法思想：算法思想：算法思想：算法思想：设顶点集设顶点集设顶点集设顶点集S(S(初值为空初值为空初值为空初值为空) )，用数组，用数组，用数组，用数组D D的每个元素的每个元素的每个元素的每个元素DijDij保存从保存从保存从保存从ViVi只只只只经过经过经过经过S S中的
10、顶点到达中的顶点到达中的顶点到达中的顶点到达VjVj的最短路径长度。的最短路径长度。的最短路径长度。的最短路径长度。 初始时令初始时令初始时令初始时令S=S=，DijDij的赋初值方式是：的赋初值方式是：的赋初值方式是：的赋初值方式是： 将图中一个顶点将图中一个顶点将图中一个顶点将图中一个顶点VkVk加入到加入到加入到加入到S S中，修改中，修改中，修改中，修改DijDij的值，修改方法的值，修改方法的值，修改方法的值，修改方法是：是：是：是：Dij=MinDij,(Dik+Dkj)Dij=MinDij,(Dik+Dkj)原因：原因：原因：原因： 从从从从ViVi只经过只经过只经过只经过S S
11、中的顶点中的顶点中的顶点中的顶点(Vk)(Vk)到达到达到达到达VjVj的路径长度可能比原的路径长度可能比原的路径长度可能比原的路径长度可能比原来不经过来不经过来不经过来不经过VkVk的路径更短。的路径更短。的路径更短。的路径更短。 重复重复重复重复，直到，直到，直到，直到GG的所有顶点都加入到的所有顶点都加入到的所有顶点都加入到的所有顶点都加入到S S中为止。中为止。中为止。中为止。算法实现：算法实现：算法实现：算法实现：for(intk=1;k=n;k+)for(intk=1;k=n;k+)for(inti=1;i=n;i+)for(inti=1;i=n;i+)for(intj=1;j=n
12、;j+)for(intj=1;j=n;j+)if(dik+dkjdij)if(dik+dkjdij)dij=dik+dkj;dij=dik+dkj;初始化条件：初始化条件：初始化条件：初始化条件：Dii=0;/Dii=0;/自己到自己为自己到自己为自己到自己为自己到自己为0 0；对角线为；对角线为；对角线为；对角线为0 0；Dij=Dij=边权，边权，边权，边权，i i与与与与j j有直接相连的边有直接相连的边有直接相连的边有直接相连的边Dij=+Dij=+，i i与与与与j j无直接相连的边。无直接相连的边。无直接相连的边。无直接相连的边。/如果是如果是如果是如果是intint数组，采用数组
13、，采用数组，采用数组，采用memset(d,0x7f,sizeof(d)memset(d,0x7f,sizeof(d)可全部初始化为一个很大的数可全部初始化为一个很大的数可全部初始化为一个很大的数可全部初始化为一个很大的数举例：举例：举例：举例： 已知下图中给定的关系，顶点个数已知下图中给定的关系，顶点个数已知下图中给定的关系，顶点个数已知下图中给定的关系，顶点个数n=100,n=100,两点之间的距离两点之间的距离两点之间的距离两点之间的距离w=1000,w=1000,求给定两点之间的最短距离求给定两点之间的最短距离求给定两点之间的最短距离求给定两点之间的最短距离. .要求：输出最短距离要求
14、：输出最短距离要求：输出最短距离要求：输出最短距离d15d15。分析：分析：分析：分析：Dij:Dij:表示顶点表示顶点表示顶点表示顶点i i到顶点到顶点到顶点到顶点j j之间的最短距离。初始化如下：之间的最短距离。初始化如下：之间的最短距离。初始化如下：之间的最短距离。初始化如下：5 515151223122313171317154915492352352413241345745702317023174949 230513230513175017501307130749704970floyed02217354202217354222051320220513201750182517501825
15、35131807351318074220257042202570初始状态：初始状态：初始状态：初始状态：02317023174949230513230513175017501307130749704970终止状态：终止状态：终止状态：终止状态：0221735420221735422205132022051320175018251750182535131807351318074220257042202570k=1:k=1:0231702317494923051323051372721750175066661307130749497272 66667070k=2:k=2:0231702317363
16、6 49492305132305137272175017501818 6666363613131818070749497272 66667070k=3:k=3:00222217173535 49492222051305137171175017501818 6666353513131818070749497171 66667070k=4:k=4:00222217173535 4242 2222051305132020175017501818 252535351313181807074242 2020 25257070参考代码：参考代码：参考代码：参考代码：#include#include#inc
17、lude#includeusingnamespacestd;usingnamespacestd;constintmaxn=101;constintmaxn=101;constintmaxw=1001;constintmaxw=1001;intdmaxnmaxn;intdmaxnmaxn;intn,p,q;intn,p,q;voidinit()voidinit()cinn;cinpq;cinn;cinpq;for(inti=1;i=n;i+)for(inti=1;i=n;i+)for(intj=1;j=n;j+)for(intj=1;jijk)while(cinijk)dij=k;dji=k;d
18、ij=k;dji=k; voidfloyed()voidfloyed()for(intk=1;k=n;k+)for(intk=1;k=n;k+)for(inti=1;i=n;i+)for(inti=1;i=n;i+)for(intj=1;j=n;j+)for(intj=1;j=n;j+)if(dik+dkjdij)if(dik+dkjdij)dij=dik+dkj;dij=dik+dkj; ;voidprint()voidprint()coutdpqendl;coutdpqendl; intmain()intmain()init();init();floyed();floyed();print
19、();print();return0;return0; （二）（二）（二）（二）floyedfloyed输出最短路径路线输出最短路径路线输出最短路径路线输出最短路径路线方法一：方法一：方法一：方法一：定义二维数组定义二维数组定义二维数组定义二维数组Pathnn(nPathnn(n为图的顶点数为图的顶点数为图的顶点数为图的顶点数) )，元素，元素，元素，元素PathijPathij保存保存保存保存从从从从ViVi到到到到VjVj的最短路径所经过的顶点。的最短路径所经过的顶点。的最短路径所经过的顶点。的最短路径所经过的顶点。初始化为初始化为初始化为初始化为Pathij=-1Pathij=-1，表示
20、从，表示从，表示从，表示从ViVi到到到到VjVj不经过任何不经过任何不经过任何不经过任何(S(S中的中中的中中的中中的中间间间间) )顶点。顶点。顶点。顶点。当某个顶点当某个顶点当某个顶点当某个顶点VkVk加入到加入到加入到加入到S S中后使中后使中后使中后使AijAij变小时，令变小时，令变小时，令变小时，令Pathij=kPathij=k。若若若若Pathij=kPathij=k：从：从：从：从ViVi到到到到VjVj经过经过经过经过VkVk，最短路径序列是，最短路径序列是，最短路径序列是，最短路径序列是(Vi,(Vi,Vk,Vj)Vk,Vj)，则路径子序列：，则路径子序列：，则路径子序
21、列：，则路径子序列：(Vi,Vk)(Vi,Vk)和和和和(Vk,Vj)(Vk,Vj)一定一定一定一定是从是从是从是从ViVi到到到到VkVk和从和从和从和从VkVk到到到到VjVj的最短路径。从而可以根据的最短路径。从而可以根据的最短路径。从而可以根据的最短路径。从而可以根据PathikPathik和和和和PathkjPathkj的值再找到该路径上所经过的其它顶点，的值再找到该路径上所经过的其它顶点，的值再找到该路径上所经过的其它顶点，的值再找到该路径上所经过的其它顶点，依此类依此类依此类依此类推。推。推。推。参考代码：参考代码：参考代码：参考代码：for(intk=1;k=n;k+)for(
22、intk=1;k=n;k+)for(inti=1;i=n;for(inti=1;i=n;i i+)+)for(intj=1;j=n;j+)for(intj=1;j=n;j+)if(dik+dkjdij)if(dik+dkjdij)dij=dik+dkj;dij=dik+dkj;pathij=k;pathij=k;初始化：初始化：初始化：初始化：pathij=-1;ipathij=-1;i与与与与j j不经过任何中间点不经过任何中间点不经过任何中间点不经过任何中间点dijdij：02317023174949 230513230513175017501307130749704970pathpath
23、ijij：-1-1 -1-1 -1-1 -1-1 -1-1 -1-1 -1-1 -1-1 -1-1 -1-1-1-1 -1-1 -1-1 -1-1 -1-1-1-1 -1-1 -1-1 -1-1 -1-1-1-1 -1-1 -1-1 -1-1 -1-1dijdij：02317023174949 230513230513175017501307130749704970pathpathijij：-1-1 -1-1 -1-1 -1-1 -1-1 -1-1 -1-1 -1-1 -1-1 -1-1-1-1 -1-1 -1-1 -1-1 -1-1-1-1 -1-1 -1-1 -1-1 -1-1-1-1 -
24、1-1 -1-1 -1-1 -1-1k=1:k=1:0231702317494923051323051372721750175066661307130749497272 66667070pathpathijij：-1-1 -1-1 -1-1 -1-1 -1-1 -1-1 -1-1 -1-1 -1-1 1 1-1-1 -1-1 -1-1 -1-1 1 1-1-1 -1-1 -1-1 -1-1 -1-1-1-1 1 1 1 1 -1-1 -1-1k=2:k=2:02317023173636 49492305132305137272175017501818 666636361313181807074
25、9497272 66667070pathpathijij：-1-1 -1-1 -1-1 2 2 -1-1 -1-1 -1-1 -1-1 -1-1 1 1-1-1 -1-1 -1-1 2 2 1 1 2 2 -1-1 2 2 -1-1 -1-1-1-1 1 1 1 1 -1-1 -1-1k=3:k=3:00222217173535 49492222051305137171175017501818 6666353513131818070749497171 66667070k=4:k=4:00222217173535 4242 2222051305132020175017501818 2525353
26、51313181807074242 2020 25257070pathpathijij：-1-1 3 3 -1-1 3 3 -1-1 3 3 -1-1 -1-1 -1-1 3 3-1-1 -1-1 -1-1 2 2 1 1 3 3 -1-1 2 2 -1-1 -1-1-1-1 3 3 1 1 -1-1 -1-1pathpathijij：-1-1 3 3 -1-1 3 3 4 4 3 3 -1-1 -1-1 -1-1 4 4-1-1 -1-1 -1-1 2 2 4 4 3 3 -1-1 2 2 -1-1 -1-14 4 4 4 4 4 -1-1 -1-1输出输出输出输出i i到到到到j j的最短
27、路径：的最短路径：的最短路径：的最短路径：voiddfs(inti,intj)/voiddfs(inti,intj)/输出输出输出输出i i到到到到j j之间的点，不包含之间的点，不包含之间的点，不包含之间的点，不包含i i和和和和j j结点；结点；结点；结点；if(pathij!=-1)if(pathij!=-1)dfs(i,pathij);dfs(i,pathij);coutpathij;coutpathij4:35:13241-4:35:1324path14=2path14=2path12=3path12=3path13=1path13=1参考代码：参考代码：参考代码：参考代码：for(
28、intk=1;k=n;k+)for(intk=1;k=n;k+)for(inti=1;i=n;k+)for(inti=1;i=n;k+)for(intj=1;j=n;j+)for(intj=1;j=n;j+)if(dik+dkjdij)if(dik+dkjdij)dij=dik+dkj;dij=dik+dkj;pathij=pathkj;pathij=pathkj;初始化：初始化：初始化：初始化：i i到到到到j j有边，则有边，则有边，则有边，则pathij=i;pathji=j;pathij=i;pathji=j;输出输出输出输出i i到到到到j j的路线的路线的路线的路线voiddfs(
29、inti,intj)voiddfs(inti,intj)if(i=j)couti;if(i=j)couti0)elseif(pathij0)dfs(i,pathi,j);dfs(i,pathi,j);coutj;coutj;dijdij：02317023174949 230513230513175017501307130749704970pathpathijij：0 0 1 1 1 1 0 0 1 1 2 2 0 0 2 2 2 2 0 03 3 3 3 0 0 0 0 0 00 0 4 4 0 0 0 0 4 45 5 0 0 0 0 5 5 0 0k=1:k=1:0231702317494
30、923051323051372721750175066661307130749497272 66667070pathpathijij：0 0 1 1 1 1 0 0 1 1 2 2 0 0 2 2 2 2 1 13 3 3 3 0 0 0 0 1 10 0 4 4 0 0 0 0 4 45 5 1 1 1 1 5 5 0 0k=2:k=2:02317023173636 49492305132305137272175017501818 6666363613131818070749497272 66667070pathpathijij：0 0 1 1 1 1 2 2 1 1 2 2 0 0 2 2
31、 2 2 1 13 3 3 3 0 0 2 2 1 12 2 4 4 2 2 0 0 4 45 5 1 1 1 1 5 5 0 0k=3:k=3:00222217173535 49492222051305137171175017501818 6666353513131818070749497171 66667070k=4:k=4:00222217173535 4242 2222051305132020175017501818 252535351313181807074242 2020 25257070pathpathijij：0 0 3 3 1 1 2 2 1 1 3 3 0 0 2 2 2
32、2 1 13 3 3 3 0 0 2 2 1 13 3 4 4 2 2 0 0 4 45 5 3 3 1 1 5 5 0 0pathpathijij：0 0 3 3 1 1 2 2 4 4 3 3 0 0 2 2 2 2 4 43 3 3 3 0 0 2 2 4 43 3 4 4 2 2 0 0 4 43 3 4 4 2 2 5 5 0 0参考代码：参考代码：参考代码：参考代码：for(intk=1;k=n;k+)for(intk=1;k=n;k+)for(inti=1;i=n;k+)for(inti=1;i=n;k+)for(intj=1;j=n;j+)for(intj=1;j=n;j+)i
33、f(dik+dkjdij)if(dik+dkjdij)dij=dik+dkj;dij=dik+dkj;pathij=pathkj;pathij=pathkj;初始化：初始化：初始化：初始化：i i到到到到j j有边，则有边，则有边，则有边，则pathij=i;pathji=j;pathij=i;pathji=j;输出输出输出输出i i到到到到j j的路线的路线的路线的路线voiddfs(inti,intj)voiddfs(inti,intj)if(i=j)couti;if(i=j)couti0)elseif(pathij0)dfs(i,pathi,j);dfs(i,pathi,j);coutj
34、;coutj;终止状态：终止状态：终止状态：终止状态：0221735420221735422205132022051320175018251750182535131807351318074220257042202570pathpathijij：0 0 3 3 1 1 2 2 4 4 3 3 0 0 2 2 2 2 4 43 3 3 3 0 0 2 2 4 43 3 4 4 2 2 0 0 4 43 3 4 4 2 2 5 5 0 0dfs(1,5)=dfs(1,4),输出输出5,dfs(1,2),输出输出4dfs(1,3),输出输出2dfs(1,1),输出输出3输出输出1输出：输出：13245
35、【综合应用举例【综合应用举例【综合应用举例【综合应用举例1 1】1 1：产生数：产生数：产生数：产生数(noip2001)(noip2001)【问题描述【问题描述【问题描述【问题描述: :】给出一个正整数给出一个正整数给出一个正整数给出一个正整数nn（n1050)n1050)和和和和kk个变换规则（个变换规则（个变换规则（个变换规则（k=15k535366上面的整数上面的整数上面的整数上面的整数234234经过变换后可能产生出的整数为（包括原数）经过变换后可能产生出的整数为（包括原数）经过变换后可能产生出的整数为（包括原数）经过变换后可能产生出的整数为（包括原数）: :234534264564
36、234534264564共共共共44种不同的产生数。种不同的产生数。种不同的产生数。种不同的产生数。【任务：】【任务：】【任务：】【任务：】给出一个整数给出一个整数给出一个整数给出一个整数nn和和和和kk个变换规则。个变换规则。个变换规则。个变换规则。求经过任意次的变换（求经过任意次的变换（求经过任意次的变换（求经过任意次的变换（0 0次或多次），能产生出多少个不同整数。仅要求输次或多次），能产生出多少个不同整数。仅要求输次或多次），能产生出多少个不同整数。仅要求输次或多次），能产生出多少个不同整数。仅要求输出个数。出个数。出个数。出个数。 【输入：】【输入：】【输入：】【输入：】第一行：第一
37、行：第一行：第一行：n n。第二行：。第二行：。第二行：。第二行：k k。以下。以下。以下。以下k k行：每行两个一位数：行：每行两个一位数：行：每行两个一位数：行：每行两个一位数：xyxy，中间一个空格，中间一个空格，中间一个空格，中间一个空格，表示一个变换规则：表示一个变换规则：表示一个变换规则：表示一个变换规则：x x可以变为可以变为可以变为可以变为y y。【输出：】【输出：】【输出：】【输出：】一个整数（满足条件的个数）：一个整数（满足条件的个数）：一个整数（满足条件的个数）：一个整数（满足条件的个数）： 【输入样例【输入样例【输入样例【输入样例1 1】2342342 22525363
38、6【样例输出【样例输出【样例输出【样例输出1 1】4 4【输入样例【输入样例【输入样例【输入样例2 2】2342347 72525282857575151797936364343【样例输出【样例输出【样例输出【样例输出2 2】3636分析：分析：分析：分析：乘法原理乘法原理乘法原理乘法原理直接进行计数。直接进行计数。直接进行计数。直接进行计数。用用用用fifi表示数字表示数字表示数字表示数字i i包括本身可以变成的数字总个数包括本身可以变成的数字总个数包括本身可以变成的数字总个数包括本身可以变成的数字总个数这里的变成可以是直接变成也可以是间接变成：这里的变成可以是直接变成也可以是间接变成：这里
39、的变成可以是直接变成也可以是间接变成：这里的变成可以是直接变成也可以是间接变成：比如比如比如比如3-5,5-7,3-5,5-7,那么那么那么那么3-73-7那么对于一个数那么对于一个数那么对于一个数那么对于一个数a a（用数组存（用数组存（用数组存（用数组存, ,长度为长度为长度为长度为n n），根据乘法原理它能产生出不同整），根据乘法原理它能产生出不同整），根据乘法原理它能产生出不同整），根据乘法原理它能产生出不同整数数量：数数量：数数量：数数量：fa1*fa2*fa3*fanfa1*fa2*fa3*fan2:62:63:23:24:34:36*2*3=366*2*3=36最多可能有最多可能
40、有最多可能有最多可能有5050位数位数位数位数 每一位最多有每一位最多有每一位最多有每一位最多有9 9种变换方法，所以最大可能种变换方法，所以最大可能种变换方法，所以最大可能种变换方法，所以最大可能950950需要模拟大数乘法需要模拟大数乘法需要模拟大数乘法需要模拟大数乘法 而每次乘数是一个不超过而每次乘数是一个不超过而每次乘数是一个不超过而每次乘数是一个不超过1010的数。的数。的数。的数。参考代码：参考代码：参考代码：参考代码：#include#include#include#include#include#includeboolf1010;boolf1010;intk,intk,ans5
41、00=1ans500=1,l=1;,l=1;usingnamespacestd;usingnamespacestd;voidwk(intx)/voidwk(intx)/高精度乘法高精度乘法高精度乘法高精度乘法 for(inti=0;il;i+)for(inti=0;il;i+)ansi*=x;ansi*=x;for(inti=0;il;i+)for(inti=0;i=10)ansi+1+=ansi/10;ansi%=10;if(ansi=10)ansi+1+=ansi/10;ansi%=10;while(ansl0)while(ansl0)ansl+1=ansl/10;ansl+1=ansl/
42、10;ansl=ansl%10;ansl=ansl%10;l+;l+; intmain()intmain()stringa;stringa;cinak;cinak;intx,y;intx,y;for(inti=1;ixy;fxy=1;for(inti=1;ixy;fxy=1;for(inti=0;i=9;i+)fii=1;/for(inti=0;i=9;i+)fii=1;/数字是可以转化为自己的数字是可以转化为自己的数字是可以转化为自己的数字是可以转化为自己的for(intk=for(intk=1 1;k=9;k+)/;k=9;k+)/用用用用floydfloyd计算每个数可以转换的数字计算每
43、个数可以转换的数字计算每个数可以转换的数字计算每个数可以转换的数字( (包括本身包括本身包括本身包括本身) )for(inti=for(inti=0 0;i=9;i+);i=9;i+)for(intj=for(intj=1 1;j=9;j+);j=9;j+)if(fik&fkj)fij=1;if(fik&fkj)fij=1;intb10;intb10;for(inti=0;i=9;i+)/for(inti=0;i=9;i+)/统计每个数可以转换的数字数统计每个数可以转换的数字数统计每个数可以转换的数字数统计每个数可以转换的数字数inttot=0;inttot=0;for(intj=for(in
44、tj=1 1;j=9;j+);j=9;j+)if(fij)tot+;if(fij)tot+;bi=tot;bi=tot;for(inti=0;ia.length();i+)for(inti=0;i=0;i-)cout=0;i-)coutansi;return0;return0; 3.5.43.5.4计算某一顶点到其它所有顶点的最短路径计算某一顶点到其它所有顶点的最短路径计算某一顶点到其它所有顶点的最短路径计算某一顶点到其它所有顶点的最短路径 （单源最短路径问题：（单源最短路径问题：（单源最短路径问题：（单源最短路径问题：dijkstradijkstra算法）算法）算法）算法）开始点（源点）：开
45、始点（源点）：开始点（源点）：开始点（源点）：startstartDi:Di:顶点顶点顶点顶点startstart到到到到i i的最短距离。的最短距离。的最短距离。的最短距离。初始：初始：初始：初始：Dstart=0Dstart=0；Di=astartiDi=astartidijkstradijkstra算法：算法：算法：算法：将顶点分为两个集合：已求得最短距离的点集合将顶点分为两个集合：已求得最短距离的点集合将顶点分为两个集合：已求得最短距离的点集合将顶点分为两个集合：已求得最短距离的点集合1 1，待求点集合，待求点集合，待求点集合，待求点集合2. 2.1 1、在集合、在集合、在集合、在集合
46、2 2中找一个到中找一个到中找一个到中找一个到startstart距离最近的顶点距离最近的顶点距离最近的顶点距离最近的顶点k:mindkk:mindk2 2、把顶点、把顶点、把顶点、把顶点k k加到集合加到集合加到集合加到集合1 1中，同时修改集合中，同时修改集合中，同时修改集合中，同时修改集合2 2中的剩余顶点中的剩余顶点中的剩余顶点中的剩余顶点j j的的的的djdj是否经是否经是否经是否经过过过过k k后变短。如果变短修改后变短。如果变短修改后变短。如果变短修改后变短。如果变短修改djdjIf(dk+akjdj)dj=dk+akjIf(dk+akjdj)dj=dk+akj3 3、重复、重复
47、、重复、重复1 1，直至集合，直至集合，直至集合，直至集合2 2空为止。空为止。空为止。空为止。数据结构：数据结构：数据结构：数据结构：FiFi：值为：值为：值为：值为truetrue，已求得最短距离，在集合，已求得最短距离，在集合，已求得最短距离，在集合，已求得最短距离，在集合1 1中；中；中；中；值为值为值为值为falsefalse，在集合，在集合，在集合，在集合2 2中；中；中；中；开始点（源点）：开始点（源点）：开始点（源点）：开始点（源点）：startstartDi:Di:顶点顶点顶点顶点startstart到到到到i i的最短距离。的最短距离。的最短距离。的最短距离。初始：初始：初
48、始：初始：Dstart=0Dstart=0；Di=astartiDi=astarti；Pathi,iPathi,i的前驱结点的前驱结点的前驱结点的前驱结点初始表：初始表：初始表：初始表：顶点顶点1 12 23 34 45 5FiFiT TF FF FF FF FDiDi0 010104949 7 7PathPathii1 11 11 11 1dijkstradijkstra算法：算法：算法：算法：将顶点分为两个集合：已求得最短距离的点集合将顶点分为两个集合：已求得最短距离的点集合将顶点分为两个集合：已求得最短距离的点集合将顶点分为两个集合：已求得最短距离的点集合1 1，待求点集合，待求点集合，
49、待求点集合，待求点集合2. 2.1 1、在集合、在集合、在集合、在集合2 2中找一个到中找一个到中找一个到中找一个到startstart距离最近的顶点距离最近的顶点距离最近的顶点距离最近的顶点k:mindkk:mindk2 2、把顶点、把顶点、把顶点、把顶点k k加到集合加到集合加到集合加到集合1 1中，同时修改集合中，同时修改集合中，同时修改集合中，同时修改集合2 2中的剩余顶点中的剩余顶点中的剩余顶点中的剩余顶点j j的的的的djdj是否是否是否是否经过经过经过经过k k后变短。如果变短修改后变短。如果变短修改后变短。如果变短修改后变短。如果变短修改djdjIf(dk+akjdj)dj=d
50、k+akjIf(dk+akjdj)dj=dk+akj3 3、重复、重复、重复、重复1 1，直至集合，直至集合，直至集合，直至集合2 2空为止。空为止。空为止。空为止。顶点顶点1 12 23 34 45 5FiFiT TF FF FF FF FDiDi0 010104949 7 7PathPathii1 11 11 11 1顶点顶点1 12 23 34 45 5FiFiT TF FF FF FT TDiDi0 01010494920207 7PathPathii1 11 11 15 51 1dijkstradijkstra算法：算法：算法：算法：将顶点分为两个集合：已求得最短距离的点集合将顶点分
51、为两个集合：已求得最短距离的点集合将顶点分为两个集合：已求得最短距离的点集合将顶点分为两个集合：已求得最短距离的点集合1 1，待求点集合，待求点集合，待求点集合，待求点集合2. 2.1 1、在集合、在集合、在集合、在集合2 2中找一个到中找一个到中找一个到中找一个到startstart距离最近的顶点距离最近的顶点距离最近的顶点距离最近的顶点k:mindkk:mindk2 2、把顶点、把顶点、把顶点、把顶点k k加到集合加到集合加到集合加到集合1 1中，同时修改集合中，同时修改集合中，同时修改集合中，同时修改集合2 2中的剩余顶点中的剩余顶点中的剩余顶点中的剩余顶点j j的的的的djdj是否是否
52、是否是否经过经过经过经过k k后变短。如果变短修改后变短。如果变短修改后变短。如果变短修改后变短。如果变短修改djdjIf(dk+akjdj)dj=dk+akjIf(dk+akjdj)dj=dk+akj3 3、重复、重复、重复、重复1 1，直至集合，直至集合，直至集合，直至集合2 2空为止。空为止。空为止。空为止。顶点顶点1 12 23 34 45 5FiFiT TF FF FF FT TDiDi0 01010494920207 7PathPathii1 11 11 15 51 1顶点顶点1 12 23 34 45 5FiFiT TT TF FF FT TDiDi0 0101027271717
53、7 7PathPathii1 11 12 22 21 1dijkstradijkstra算法：算法：算法：算法：将顶点分为两个集合：已求得最短距离的点集合将顶点分为两个集合：已求得最短距离的点集合将顶点分为两个集合：已求得最短距离的点集合将顶点分为两个集合：已求得最短距离的点集合1 1，待求点集合，待求点集合，待求点集合，待求点集合2. 2.1 1、在集合、在集合、在集合、在集合2 2中找一个到中找一个到中找一个到中找一个到startstart距离最近的顶点距离最近的顶点距离最近的顶点距离最近的顶点k:mindkk:mindk2 2、把顶点、把顶点、把顶点、把顶点k k加到集合加到集合加到集合
54、加到集合1 1中，同时修改集合中，同时修改集合中，同时修改集合中，同时修改集合2 2中的剩余顶点中的剩余顶点中的剩余顶点中的剩余顶点j j的的的的djdj是否是否是否是否经过经过经过经过k k后变短。如果变短修改后变短。如果变短修改后变短。如果变短修改后变短。如果变短修改djdjIf(dk+akjdj)dj=dk+akjIf(dk+akjdj)dj=dk+akj3 3、重复、重复、重复、重复1 1，直至集合，直至集合，直至集合，直至集合2 2空为止。空为止。空为止。空为止。顶点顶点1 12 23 34 45 5FiFiT TT TF FF FT TDiDi0 01010272717177 7P
55、athPathii1 11 12 22 21 1顶点顶点 1 1 2 23 34 45 5FiFiT TT TF FT TT TDiDi0 0 1 10 02 27 71 17 77 7PatPathihi1 1 1 12 22 21 1顶点顶点 1 1 2 23 34 45 5FiFiT TT TT TT TT TDiDi0 0 1 10 02 27 71 17 77 7PatPathihi1 1 1 12 22 21 1数据输入：数据输入：数据输入：数据输入：5 51 112101210157157231723172472472552553434343445134513参考代码：参考代码：
56、参考代码：参考代码：#include#include#include#includeusingnamespacestd;usingnamespacestd;constintmaxn=101;constintmaxn=101;intfmaxn,amaxnmaxn,dmaxn,pathmaxn;intfmaxn,amaxnmaxn,dmaxn,pathmaxn;intn,start;intn,start;constintinf=99999;constintinf=99999;voidinit()voidinit()cinnstart;cinnstart;intx,y,w;intx,y,w;for(
57、inti=1;i=n;i+)for(inti=1;i=n;i+)for(intj=1;j=n;j+)for(intj=1;jxyw)while(cinxyw)axy=w;axy=w;ayx=w;ayx=w; voiddijkstra(ints)voiddijkstra(ints)for(inti=1;i=n;i+)di=asi;fi=false;pathi=s;for(inti=1;i=n;i+)di=asi;fi=false;pathi=s;fs=true;/fs=true;/加入集合加入集合加入集合加入集合1 1for(inti=2;i=n;i+)for(inti=2;i=n;i+)int
58、mind=inf;intmind=inf;intk=0;/intk=0;/用来记录准备放入集合用来记录准备放入集合用来记录准备放入集合用来记录准备放入集合1 1的点的点的点的点for(intj=1;j=n;j+)/for(intj=1;j=n;j+)/查找集合查找集合查找集合查找集合2 2中中中中dd最小的点最小的点最小的点最小的点if(!fj)&(djmind)mind=dj;k=j;if(!fj)&(djmind)mind=dj;k=j;if(mind=inf)break;/if(mind=inf)break;/更新结点求完了更新结点求完了更新结点求完了更新结点求完了fk=true;/fk
59、=true;/加入集合加入集合加入集合加入集合1 1for(intj=1;j=n;j+)/for(intj=1;j=n;j+)/修改集合修改集合修改集合修改集合2 2中的中的中的中的djdjif(!fj)&(dk+akjdj)if(!fj)&(dk+akjdj)dj=dk+akj;pathj=k;dj=dk+akj;pathj=k; voiddfs(inti)voiddfs(inti)if(i!=start)dfs(pathi);if(i!=start)dfs(pathi);couti;couti; voidwrite()voidwrite()coutstartcoutstart到其余各点的最
60、短距离是：到其余各点的最短距离是：到其余各点的最短距离是：到其余各点的最短距离是：endl;endl;for(inti=1;i=n;i+)for(inti=1;i=n;i+)if(i!=start)if(i!=start)if(di=inf)coutiif(di=inf)couti不可达！不可达！不可达！不可达！;elseelsecouticouti的最短距离：的最短距离：的最短距离：的最短距离：di,di,依次经过的点是：依次经过的点是：依次经过的点是：依次经过的点是：;dfs(pathi);dfs(pathi);coutiendl;coutiendl; intmain()intmain()
61、init();init();dijkstra(start);dijkstra(start);write();write(); 例例例例1 1：最短路径问题：最短路径问题：最短路径问题：最短路径问题【问题描述】【问题描述】【问题描述】【问题描述】平面上有平面上有平面上有平面上有n n个点（个点（个点（个点（n=100n=100），每个点的坐标均在），每个点的坐标均在），每个点的坐标均在），每个点的坐标均在-1000010000-1000010000之间。其中之间。其中之间。其中之间。其中的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间的一些点之间有连线。若有连线，则表示可从一
62、个点到达另一个点，即两点间的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。之间的最短路径。之间的最短路径。之间的最短路径。【输入格式】【输入格式】【输入格式】【输入格式】 输入文件为输入文件为输入文件为输入文件为short.
63、inshort.in，共，共，共，共n+m+3n+m+3行，其中行，其中行，其中行，其中: :第一行为整数第一行为整数第一行为整数第一行为整数n n。 第第第第2 2行到第行到第行到第行到第n+1n+1行（共行（共行（共行（共n n行）行）行）行） ，每行两个整数，每行两个整数，每行两个整数，每行两个整数x x和和和和y y，描述了一个点的坐标。，描述了一个点的坐标。，描述了一个点的坐标。，描述了一个点的坐标。 第第第第n+2n+2行为一个整数行为一个整数行为一个整数行为一个整数mm，表示图中连线的个数。，表示图中连线的个数。，表示图中连线的个数。，表示图中连线的个数。 此后的此后的此后的此后
64、的mm行，每行描述一条连线，由两个整数行，每行描述一条连线，由两个整数行，每行描述一条连线，由两个整数行，每行描述一条连线，由两个整数i i和和和和j j组成，表示第组成，表示第组成，表示第组成，表示第i i个点和第个点和第个点和第个点和第j j个点之间有连线。个点之间有连线。个点之间有连线。个点之间有连线。 最后一行：两个整数最后一行：两个整数最后一行：两个整数最后一行：两个整数s s和和和和t t，分别表示源点和目标点。，分别表示源点和目标点。，分别表示源点和目标点。，分别表示源点和目标点。 【输出格式】【输出格式】【输出格式】【输出格式】 输出文件为输出文件为输出文件为输出文件为shor
65、t.outshort.out，仅一行，一个实数（保留两位小数），表示从，仅一行，一个实数（保留两位小数），表示从，仅一行，一个实数（保留两位小数），表示从，仅一行，一个实数（保留两位小数），表示从s s到到到到t t的最的最的最的最短路径长度。短路径长度。短路径长度。短路径长度。【输入样例】【输入样例】【输入样例】【输入样例】5 5000020202222020231315 5121213131414252535351515【输出样例】【输出样例】【输出样例】【输出样例】3.413.41【来源】【来源】【来源】【来源】http:/ f数组为最大值数组为最大值数组为最大值数组为最大值for(i=
66、1;i=m;i+)/for(i=1;ixy;cinxy;fyx=fxy=sqrt(pow(double(ax1-fyx=fxy=sqrt(pow(double(ax1-ay1),2)+pow(double(ax2-ay2),2);ay1),2)+pow(double(ax2-ay2),2);/pow(x,y)/pow(x,y)表示表示表示表示xyxy，其中，其中，其中，其中x,yx,y必须为必须为必须为必须为doubledouble类型，要用类型，要用类型，要用类型，要用cmathcmath库库库库cinse;cinse;for(k=1;k=n;k+)/floyedfor(k=1;k=n;k+
67、)/floyed最短路算法最短路算法最短路算法最短路算法for(i=1;i=n;i+)for(i=1;i=n;i+)for(j=1;j=n;j+)for(j=1;j=n;j+)if(i!=j)&(i!=k)&(j!=k)&(fik+fkjfij)if(i!=j)&(i!=k)&(j!=k)&(fik+fkjfij)fij=fik+fkj;fij=fik+fkj;printf(%.2lfn,fse);printf(%.2lfn,fse);return0;return0; 例例例例2 2：最小花费：最小花费：最小花费：最小花费【问题描述】【问题描述】【问题描述】【问题描述】在在在在n n个人中，某
68、些人的银行账号之间可以互相转账。这些人个人中，某些人的银行账号之间可以互相转账。这些人个人中，某些人的银行账号之间可以互相转账。这些人个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转之间转账的手续费各不相同。给定这些人之间转账时需要从转之间转账的手续费各不相同。给定这些人之间转账时需要从转之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问账金额里扣除百分之几的手续费，请问账金额里扣除百分之几的手续费，请问账金额里扣除百分之几的手续费，请问A A最少需要多少钱使得最少需要多少钱使得最少需要多少钱使得最少需
69、要多少钱使得转账后转账后转账后转账后B B收到收到收到收到100100元。元。元。元。【输入格式】【输入格式】【输入格式】【输入格式】第一行输入两个正整数第一行输入两个正整数第一行输入两个正整数第一行输入两个正整数n,mn,m，分别表示总人数和可以互相转，分别表示总人数和可以互相转，分别表示总人数和可以互相转，分别表示总人数和可以互相转账的人的对数。账的人的对数。账的人的对数。账的人的对数。以下以下以下以下mm行每行输入三个正整数行每行输入三个正整数行每行输入三个正整数行每行输入三个正整数x,y,zx,y,z，表示标号为，表示标号为，表示标号为，表示标号为x x的人和标号的人和标号的人和标号的
70、人和标号为为为为y y的人之间互相转账需要扣除的人之间互相转账需要扣除的人之间互相转账需要扣除的人之间互相转账需要扣除z%z%的手续费的手续费的手续费的手续费(z100)(z100)。最后一行输入两个正整数最后一行输入两个正整数最后一行输入两个正整数最后一行输入两个正整数A,BA,B。数据保证。数据保证。数据保证。数据保证A A与与与与B B之间可以直接之间可以直接之间可以直接之间可以直接或间接地转账。或间接地转账。或间接地转账。或间接地转账。【输出格式】【输出格式】【输出格式】【输出格式】输出输出输出输出A A使得使得使得使得B B到账到账到账到账100100元最少需要的总费用。精确到小数点
71、后元最少需要的总费用。精确到小数点后元最少需要的总费用。精确到小数点后元最少需要的总费用。精确到小数点后8 8位。位。位。位。【输入样例】【输入样例】【输入样例】【输入样例】33331211212322321331331313【输出样例】【输出样例】【输出样例】【输出样例】103.07153164103.07153164【数据规模】【数据规模】【数据规模】【数据规模】1=n=20001=n=2000【来源】【来源】【来源】【来源】http:/ A到到到到B B的最短路径问题，解题的关键是构图：的最短路径问题，解题的关键是构图：的最短路径问题，解题的关键是构图：的最短路径问题，解题的关键是构图：
72、以人员编号为顶点，若以人员编号为顶点，若以人员编号为顶点，若以人员编号为顶点，若x x号人和号人和号人和号人和y y号人之间可以相互转账则在号人之间可以相互转账则在号人之间可以相互转账则在号人之间可以相互转账则在x x和和和和y y之间连一条之间连一条之间连一条之间连一条边，边的权为边，边的权为边，边的权为边，边的权为100/100/（100-z100-z）。对于样例构图如下：）。对于样例构图如下：）。对于样例构图如下：）。对于样例构图如下： 因为因为因为因为B B到帐后收到到帐后收到到帐后收到到帐后收到100100元，所以，原题等价于求从元，所以，原题等价于求从元，所以，原题等价于求从元，所
73、以，原题等价于求从B B到到到到A A的最短路径（权值相的最短路径（权值相的最短路径（权值相的最短路径（权值相乘），由于乘法满足交换律，故也可求从乘），由于乘法满足交换律，故也可求从乘），由于乘法满足交换律，故也可求从乘），由于乘法满足交换律，故也可求从A A到到到到B B的最短路径。对于样例，从的最短路径。对于样例，从的最短路径。对于样例，从的最短路径。对于样例，从A A到到到到B B的最短路径为：的最短路径为：的最短路径为：的最短路径为：123123，权值为：，权值为：，权值为：，权值为：100/(100-1)*100/(100-2)=100/(100-1)*100/(100-2)=1.0
74、3071531641.0307153164，最后的结果为：，最后的结果为：，最后的结果为：，最后的结果为：103.07153164103.07153164（保留小数点后（保留小数点后（保留小数点后（保留小数点后8 8位）位）位）位）【参考程序】【参考程序】【参考程序】【参考程序】#include#includeusingnamespacestd;usingnamespacestd;doublea20012001,dis2001=0,minn;doublea20012001,dis2001=0,minn;intn,m,i,j,k,x,y,f2001=0;intn,m,i,j,k,x,y,f200
75、1=0;voidinit()voidinit() cinnm;cinnm;for(i=1;i=m;i+)for(i=1;ixy;cinxy; voiddijkstra(intx)voiddijkstra(intx) for(i=1;i=n;i+)disi=axi;for(i=1;i=n;i+)disi=axi;disx=1;fx=1;disx=1;fx=1;for(i=1;i=n-1;i+)for(i=1;i=n-1;i+)minn=0;minn=0;for(j=1;j=n;j+)for(j=1;jminn)k=j;minn=disj;if(fj=0&disjminn)k=j;minn=disj;fk=1;fk=1;if(k=y)break;if(k=y)break;for(j=1;j=n;j+)for(j=1;jdisj)disj=disk*akj;if(fj=0&disk*akjdisj)disj=disk*akj; intmain()intmain()init();init();dijkstra(x);dijkstra(x);printf(%0.8lf,100/disy);printf(%0.8lf,100/disy);return0;return0;
