图论模型及其算法.ppt

《图论模型及其算法.ppt》由会员分享，可在线阅读，更多相关《图论模型及其算法.ppt（85页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、NOIp图论算法与模型构建图论算法与模型构建长沙市一中长沙市一中 曹利国曹利国图的存储结构图的存储结构:两点之间是否有两点之间是否有边。边。Aij=0或或1（需要（需要n*n的的二维数组）二维数组）稀疏图：顶点多，边数少；稀疏图：顶点多，边数少；稠密图：顶点少，边数多；稠密图：顶点少，边数多；完全图：每两条边都有一个顶完全图：每两条边都有一个顶点。点。图的遍历：图的遍历：dfs，bfs图的连通性：对一个图，可以分图的连通性：对一个图，可以分解为多个连通分量。解为多个连通分量。如何找到一个生成树：如何找到一个生成树：MST最小最小生成树：生成树：一个有一个有 n 个结点的连通图的生成树个结点的连

2、通图的生成树是原图的极小连通子图，且包含原图中的所有是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图联通的最少的边。个结点，并且有保持图联通的最少的边。网络流的流量问题（网络流的流量问题（noi）匹配问题匹配问题图结构n图结构包括：图结构包括：n点点n边边n图涉及到的概念图涉及到的概念n边的权边的权n点的度点的度图的储存结构n矩阵矩阵n邻接表邻接表n邻接多重表邻接多重表n十字链表十字链表无向图邻接表15243123451|5|4|3|/2|2|2|3|1|2|4|/5|/4|/5|/邻接链表n每一个顶点n有一个所有与之相邻的链表n每一条边n2个（对无向图）n要在两个顶点的链表

3、中都加入n空间复杂度O(|E|)对稀疏图这种方式比较好邻接表Pascal语言 const maxv=10000;type Tnode=record /定义顶点类型 c:integer;/顶点编号 next:Tnode;/此点的邻接链表end;Var/数组g表示每个顶点的邻接链表/的链表头-哨兵 g:array1.maxv of Tnode;n,m,i,a,b:integer;t:Tnode;C+语言#include using namespace std;const int maxv=10000;struct Tnode /定义顶点类型 int c;/顶点编号 Tnode *next;/此点的

4、邻接链表;/数组g表示每个顶点的邻接链表/的链表头-哨兵 Tnode gmaxv;int n,m,i,a,b;Tnode *t;图G有n个顶点，编号从1到n。有m条有向边，输入时每行两个整数ab，表示边为从顶点a连接到顶点b。下面程序用指针实现图的邻接链表。Pascal语言 procedure ins(x:integer;var p:Tnode);Begin /插入链表子过程 new(t);t.c:=x;t.next:=p.next;p.next:=t;end;begin readln(n,m);/初始化邻接链表“哨兵”for i:=1 to n do gi.next:=nil;/读入边，插入

5、邻接链表 for i:=1 to m do begin readln(a,b);ins(b,ga);ins(a,gb);/无向边时再加入 end;/.C+语言 void ins(int x,Tnode&p)/插入链表子过程 t=new(Tnode);t-c=x;t-next=p.next;p.next=t;int main()cin n m;/初始化邻接链表“哨兵”for(i=1;i=n;i+)gi.next=NULL;for(i=0;iab;ins(b,ga);/ins(a,gb);/无向边时 /邻邻接接表表的的实现实现A（指指针针）Pascal语言 const maxV=1000;/最多顶

6、点数 maxE=10000;/最多边数type Tnode=record/定义顶点类型 c:integer;/节点编号 next:integer;/此节点的邻接链表end;var e:array1.maxE of Tnode;g:array1.maxV of Tnode;n,m,efree,i,a,b,t:integer;procedure ins(x:integer;var p:Tnode);begin /取一个空元素插入链表p后 eefree.c:=x;eefree.next:=p.next;p.next:=efree;efree:=efree+1;/新空元素下标end;C+语言 cons

7、t int maxV=1000,/最多顶点数 maxE=10000;/最多边数struct Tnode /定义顶点类型 int c;/顶点编号 int next;/此点的邻接链表;/数组g表示每个顶点的邻接链表/的链表头-哨兵 Tnode gmaxV,emaxE;int n,m,i,a,b,efree,t;void ins(int x,Tnode&p)/取一个空元素插入链表p后 eefree.c=x;eefree.next=p.next;p.next=efree;efree+;/新空元素下标邻邻接接表表的的实现实现B（数数组）Pascal语言 begin readln(n,m);/初始化邻接链

8、表“哨兵”for i:=1 to n do gi.next:=-1;efree:=1;/读入边，插入邻接链表 for i:=1 to m do begin readln(a,b);ins(b,ga);ins(a,gb);/无向边时 end;.C+语言 int main()cin n m;efree=0;/初始化邻接链表“哨兵”for(i=1;i=n;i+)gi.next=-1;/读入边，插入邻接链表 for(i=0;iab;ins(b,ga);/ins(a,gb);/无向边时 邻邻接接表表的的实现实现B（数数组）nTypenLink=Node;nNode=Recordnv,w:Longint;

9、顶点和费用nNext:Link;nEnd;nMap:Array1.MaxnofLink;用临接表记录的图nRead(n,m,s,t);nFori:=1tomdonBeginnRead(a,b,c);nNew(p);np.v:=b;p.w:=c;np.Next:=Mapa;nMapa:=p;nEnd;图的遍历从图中某一顶点出发，按某种搜索方法访遍其余顶点，且使每一顶点仅被访问一次。这一过程称为图的遍历。遍历图的基本搜索方法有两种：深度优先搜索DFS和广度优先搜索BFS。这两种方法都适用于有向图和无向图。图的深度优先搜索遍历 图的深度优先遍历DFS算法是每次在访问完当前顶点后，首先访问当前顶点的一

10、个未被访问过的邻接顶点，然后去访问这个邻接点的一个未被访问过的邻接点，这样的算法是一个递归算法。连通图的深度优先遍历算法思想。连通图的深度优先遍历算法思想。（1）访问初始顶点v并标记顶点v已访问。（2）查找顶点v的第一个邻接顶点w。（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。（5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi转到步骤（3）。直到连通图中所有顶点全部访问过为止。深度优先遍历的程序实现：（深度优先遍历的程序实现：（邻接表、Pascal）/图的一般结构 type grap

11、h_node=record end;type AdjList=record id:integer;next:AdjList;end;var n_nodes,S_i:integer;nodes:array1.maxN of graph_node;visited:array1.maxNof integer;adj:array1.maxN of AdjList;标识项点有没有访问过每个顶点都有邻接链表邻接链表的节点数据结构深度优先遍历的程序实现：（深度优先遍历的程序实现：（邻接表、Pascal）置每个点标识为“未访问”从所有未被访问的点k出发，调用DFS(k)procedure search();b

12、egin k:integer;for k:=1 to n_nodes do visitedk:=0;for k:=1 to n_nodes do if visitedk0 then DFS(k);end;置被访问节点的“时间”-次序访问k的所有相邻的节点 procedure DFS(k:integer);begin/从k出发搜索 var j:AdjList;begin inc(S_i);visitedk:=S_i;j:=adjk;while(jNULL)do begin if visitedj.id0 then DFS(j.id);j:=j.next;end;end;图的广度优先搜索遍历图的广

13、度优先遍历BFS算法是一个分层搜索的过程，和树的层序遍历算法类同，它也需要一个队列以保持遍历过的顶点顺序，以便按出队的顺序再去访问这些顶点的邻接顶点。连通图的广度优先遍历算法思想。连通图的广度优先遍历算法思想。（1）顶点v入队列。（2）当队列非空时则继续执行，否则算法结束。（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。（4）查找顶点v的第一个邻接顶点col。（5）若v的邻接顶点col未被访问过的，则col入队列。（6）继续查找顶点v的另一个新的邻接顶点col，转到步骤（5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。宽度优先遍历的程序实现宽度优先遍历的程序实现：（

14、：（邻接表、C+）/图的一般结构 struct graph_node ;struct AdjList int id;AdjList*next;int n_nodes,S_index=0;graph_node nodes maxN;int visited maxN;AdjList*adj maxN;标识项点有没有访问过每个顶点都有邻接链表邻接链表的节点数据结构宽度优先遍历的程序实现宽度优先遍历的程序实现:（邻接表、C+）置每个点标识为“未访问”从所有未被访问的点k出发，调用BFS(k)void search()int k;for(k=0;kn_nodes;k+)visitedk=0;for(k=

15、0;kn_nodes;k+)if(!visitedk)BFS(k);宽度优先遍历的程序实现宽度优先遍历的程序实现：（：（邻接表、C+）int q maxN;void BFS(int k)int front,back;q0=k;front=back=0;for(;fronnext)if(!visitedj-id)q+back=j-id;visitedj-id=+S_index;BFS用的队列，一般全局Front=back,队列不空访问k的所有相邻的节点 图的连通性问题n有向图的强有向图的强连通子图连通子图n生成树问题生成树问题强连通子图n有向图的强连通子有向图的强连通子图图n强连通子图中，任强连

16、通子图中，任两个节点都直接或两个节点都直接或间接相连间接相连n以深度优先搜索为以深度优先搜索为基础的算法基础的算法14278536生成树问题n无向图的最小生成树（贪心思想）无向图的最小生成树（贪心思想）nPrim算法，适用于点少的图算法，适用于点少的图nKruskal算法，适用于边少的图算法，适用于边少的图n有向图的最小树形图有向图的最小树形图局域网局域网(net)某局域网内有某局域网内有n(nn(n=100)=100)台计算机，由于建网时台计算机，由于建网时工作人员的疏忽，现在网内存在回路，造成网络卡的工作人员的疏忽，现在网内存在回路，造成网络卡的现象。现象。我们用我们用f(i,jf(i,j

17、)表示表示i,ji,j之间连接的畅通程度之间连接的畅通程度(f(i,jf(i,j)=1000)=disy n 松驰松驰 若在处理过程中，有两点若在处理过程中，有两点x、y出现不符合出现不符合“三角形定理三角形定理”，则可改进一下，则可改进一下松驰松驰：if(disx+lenxy disy)disy=disx+lenxy;最短路径(ShortestPath)-属性属性XYS 如果边没有如果边没有负权负权的，我们可以用类似的，我们可以用类似Prim算法的贪心算法算法的贪心算法Dijkstra算法算法。n算法描述算法描述1：SP_Dijkstra(G,s)(1)将将G中顶点分成两个集合中顶点分成两个

18、集合A、B，A集合中由已经求集合中由已经求出最短路径的顶点组成，出最短路径的顶点组成，B集合是其它顶点。开始时集合是其它顶点。开始时A中只有一个点中只有一个点s (2)从从B集合中取一个当前最短的顶点集合中取一个当前最短的顶点v (3)把把v加入加入A集合，并对集合，并对v相连的顶点试做相连的顶点试做“松驰松驰”(4)如果如果|A|=|V|，结束。否则转，结束。否则转(2)最短路径-Dijkstra算法算法Dijkstra算法nDijkstra算法中心算法中心 +124331632+0Dist值值4321节点号节点号3 32 26 6 5 5 4 4选择选择标记标记扩展扩展n算法描述算法描述2

19、：SP_Dijkstra(G,s)/求单源求单源s到其它到其它点的最短距离点的最短距离 for i=1 to n do disi /初始化每点到初始化每点到s距离距离 inAi false /设顶点不在设顶点不在A中中diss 0 /将将diss设为设为0，准备取出，准备取出for i=1 to n do v get-min()/取取dis?中最小的值中最小的值c和顶点和顶点v,inA v true /v放入放入A中中 updata(v)/检查检查(v,B),松驰松驰dis?sum sum+c /c加入加入MST的总和中的总和中最短路径-Dijkstra算法算法与prim不相同点cooking

20、 Bessie喜欢为在外面的奶牛做晚餐，喜欢为在外面的奶牛做晚餐，Bessie按响铃按响铃给他们一个信号叫他们进来就可以了。给他们一个信号叫他们进来就可以了。晚餐将在晚餐将在T(1=T=1,000,000)毫秒完成，而毫秒完成，而且且Bessie强调那些想吃她晚餐的奶牛必须准时到。强调那些想吃她晚餐的奶牛必须准时到。这些牛在这些牛在F(1=F=500)各不同的草地标号为各不同的草地标号为1F用用P(1=P=10,000)个双向的小路连接。个双向的小路连接。Bessie在第在第1个草地，个草地，给出一头牛走每一条小路所给出一头牛走每一条小路所用的时间，问多少个草地上的奶牛可以在用的时间，问多少个

21、草地上的奶牛可以在T毫秒内到毫秒内到Bessie 所在的草地，假设多头牛可以共享一条路。所在的草地，假设多头牛可以共享一条路。最短路径-实例例 如果边有如果边有负权负权的话，的话，Dijkstra算法算法是错误的。这是错误的。这里需要不断里需要不断迭代迭代地做地做“松驰松驰”，直到无，直到无“松驰松驰”为为止。止。n算法描述算法描述3：SP_Bellman(G,s)(1)初始化每点到初始化每点到s点的最短距离为点的最短距离为 (2)取所有边取所有边(x,y)，看，看x能否对能否对y松驰。松驰。(3)如果没有任何松驰，则结束如果没有任何松驰，则结束break。(4)如果松驰次数如果松驰次数N，转

22、，转(2)(5)否则，图中有否则，图中有“负圈负圈”。最短路径-Bellman-ford算法算法算法说明算法说明：nBellman-ford算法算法N次迭代就可以判断图中是否次迭代就可以判断图中是否有有“负环负环”。n取所有边有两种方法：取所有边有两种方法：(1)扫描每一点的邻接链表扫描每一点的邻接链表 (2)用有序点对用有序点对(x,y)记录边时，可直接取边。记录边时，可直接取边。但要请注意对无向图，要注意但要请注意对无向图，要注意(y,x)也要松驰。也要松驰。n对于求对于求s到某点到某点t的最短距离，可能因为其它地方的最短距离，可能因为其它地方有有“负环负环”而出现问题，要预处理。而出现问

23、题，要预处理。最短路径-Bellman-ford算法算法n算法描述算法描述4：SP_Bellman(G,s)/求单源求单源s到其它点的最短距离到其它点的最短距离 for i=1 to n do disi /初始化每点到初始化每点到s距离距离diss 0 /将将diss设为设为0for i=1 to n do /最多迭代最多迭代n rel=false;/是否有松驰标志是否有松驰标志 for 每条边每条边(x,y)/取图的每一条边取图的每一条边 if(disx+lenxy0)do v qhead;/队头节点队头节点v for 每条边每条边(v,i)/与与v相连的每一条边相连的每一条边 if(dis

24、v+lenvidisi)/不满足三角形性质不满足三角形性质 disi disv+lenvi;/松驰松驰disi if(visi=false)/不在队列，则加入队列不在队列，则加入队列 visi true;count+1;tail+1;qtail=i;visv false;head+1;count-1;/v出队列出队列最短路径-SPFA算法算法n求每对节点之间最短距离问题：例如，求一个图求每对节点之间最短距离问题：例如，求一个图的直径，即所有最短路径中最长的。的直径，即所有最短路径中最长的。n 如果多次调用单源最短路径算法，效果并不好。如果多次调用单源最短路径算法，效果并不好。特别是对有负边的图

25、。特别是对有负边的图。n如果如果无负环无负环，则有简单的，则有简单的Floyd-warshell算法。算法。这是动态规划算法。这是动态规划算法。最短路径-Floyd算法算法动态规划算法动态规划算法n定义定义d i,j,k 为为n路径中间只允许经过节点1k的情况下ni到j的最短路距离n它有两种情况它有两种情况n最短路经过点k，di,j,k=di,k,k-1+dk,j,k-1n最短路不经过点k，di,j,k=di,j,k-1n 综合起来，状态转移方程为综合起来，状态转移方程为di,j,k=min di,k,k-1+dk,j,k-1,di,j,k-1 n边界条件边界条件di,j,0=lenij（不存

26、在的边权可为）最短路径-Floyd算法算法算法描述算法描述6：SP_Floyd(G)/求每对节点的最短距离求每对节点的最短距离 for i=1 to n do for j=1 to n do disi,j lenij;/初始化边界条件初始化边界条件for k=1 to n do /K放在最外层，数组少一维放在最外层，数组少一维 for i=1 to n do for j=1 to n do if(disi,k+diskjdisi,j)/状态转移状态转移 disi,j disik+diskj;最短路径-Floyd算法算法nDijkstran单源单源 非负非负 O(|V|2)对稠密图好对稠密图好n

27、可用可用“堆堆”优化优化O(|E|*log|V|)对稀疏图较好对稀疏图较好nBellman-Fordn单源单源 无负环无负环 O(|V|*|E|)n可先用可先用Dijkstra预处理优化预处理优化nSPFA用更新队列优化用更新队列优化,时间复杂度平均好，但不确定。时间复杂度平均好，但不确定。nFloydn全源全源 无负环无负环 O(|V|2)最短路径-算法比算法比较网络流与匹配问题n网络最大流网络最大流n最小费用最大流最小费用最大流n二分图的最大匹配二分图的最大匹配n二分图的最佳匹配二分图的最佳匹配网络流算法n寻找增广链，并根据增广链修改流寻找增广链，并根据增广链修改流量。重复这一步骤，直到不

28、再存在量。重复这一步骤，直到不再存在增广链。增广链。n如果需要在此基础上求最小费用最如果需要在此基础上求最小费用最大流，只需从增广链的选择上着手。大流，只需从增广链的选择上着手。二分图与匹配算法n二分图的匹配算法又称匈牙利算法二分图的匹配算法又称匈牙利算法n匈牙利算法的中心匈牙利算法的中心可增广轨可增广轨n不断寻找可增广轨，并根据可增广不断寻找可增广轨，并根据可增广轨修改匹配轨修改匹配n最佳匹配只是在选择可增广轨时，最佳匹配只是在选择可增广轨时，将匹配的权值作为选择的条件将匹配的权值作为选择的条件图的应用(模型构建)例题1:(TRAVEL)一个城市中有一个城市中有N个车站，已知个车站，已知M条

29、连接这条连接这些车站的公共汽车单向路线，设计算法求出从些车站的公共汽车单向路线，设计算法求出从第一号车站到第第一号车站到第N号车站的最少换车次数号车站的最少换车次数.分析n这道题粗看起来似乎不太简单，但我们仔细分析这道题粗看起来似乎不太简单，但我们仔细分析一下题目就会发现，这道题实际上可以转化为最短一下题目就会发现，这道题实际上可以转化为最短路径问题来进行求解。路径问题来进行求解。n 考虑经过的所有路线中，每条路线都只保留一考虑经过的所有路线中，每条路线都只保留一头一尾两个车站，则经过的车站数目再减头一尾两个车站，则经过的车站数目再减2实际上实际上就是所求的换车次数了。要使换车次数最少，也就就

30、是所求的换车次数了。要使换车次数最少，也就是要找从是要找从1到到N的一条最短路径。而图中的边也需的一条最短路径。而图中的边也需要重新设计。要重新设计。在每一条路线中，任两个结点均由在每一条路线中，任两个结点均由其中的前者向后者连一条边，然后将每条边的长度其中的前者向后者连一条边，然后将每条边的长度都定为都定为1。利用图论模型进行构造例题2：圆桌吃饭问题n个人围着一张圆桌吃饭，每个人都不愿意两天与同一人为邻，问最多能坐多少天，并给出一种排列方案？查分约束系统转化为图论模型n设G=(V,E)为一完全图，|V|=n。图中的每个顶点代表一个人，连结顶点的边表示人之间的相邻关系。因此，每种围绕圆桌的吃饭

31、方案就成为图中的一条哈密尔顿回路。设L=为G中的一条哈密尔顿回路，其中所含的边的集合记为e(L)。问题转化为：n求m与L1,L2,Lm，使得e(Li)e(Lj)=，n并且m达到最大值。构造方法n作一圆，把圆周分成n-1等分，标上n-1个刻度，将顶点1至n-1依次排列在圆周上，顶点n放在圆心。先从圆心出发，向任意点连一条线，再从这点出发，沿圆周向左右两个方向迂回连线，直到连完圆周上所有的点，再连回圆心。这样就构造出一条哈密尔顿回路。保持所有的顶点位置不变，把所有连线围绕圆心逆时针方向旋转一个刻度，得到一条新的哈密尔顿回路。这样连续旋转(n-1)div2次，就得到了(n-1)div2条回路。nN=

32、5当n=5时构造图象，充分展示各变量之间的关系构造图象，充分展示各变量之间的关系【例3】01串问题(NOI)给定N,L0,A0,B0,L1,A1,B1，设计一个长度为N的01串，使得对于任何连续的长度为L0的子串，0的个数大于等于A0,且小于等于B0,对于任何连续的长度为L1的子串，1的个数大于等于A1且小于B1。【解题分析】模式1分析不等式设hi为01子串s0.si(1=I=n)中1的个数，其中s0=0,h0=0。显然，由hi的定义可以得出不等式0=hi-1=hi,hi=hi-1+1,移项即得：0=hi-hi-1-1=hi-1-hiL0-b0=L0时，根据条件，Si-L0+1Si中0的个数(

33、L0-(hi-hi-L0)在a0b0之间，即a0=L0-(hi-hi-L0)=b0a0-L0=hi-L0-hi-b1=L1时，根据条件，Si-L1+1Si中1的个数(hi-hi-L1)在a1b1之间，即a1=hi-hi-L1=b1。a1=hi-hi-L1一旦有了h序列，我们可以由左至右构造s串：如果hi-1=hi，则说明si=0；否则si=1(1=I=n)。由此看来，问题的关键是如何计算h序列。仔细观察上述推论条件，发现有以下特点：（1）除h0=0外，其余的条件都是由“=”连接的不等式（2）每个不等式都是含两个h未知数、一个常数的一次不等式；可见，所有不等式都整理成了k=hi-hj它给我们启示

34、，上述不等式类似于连接两点的一条有向边。因此，我们联想到信息学解题中常用的图论知识。模型2构造有向图G我们构造有向图G，如图：其中vi代表s串中的第I位。若k=vi-vj,则vi向vj引出一条权为k的有向边,表明sisj中至少需增加k个1（k为正值）或减少k个1(k为负值)。由此得出构造有向图G的方法：0=hi-hi-1-1=hi-1-hia0-L0=hi-L0-hiL0-b0=hi-hi-l0a1=hi-hi-L1-b1=hi-l1-hi计算图G的最长路径：我们已构造了一个有n+1个顶点的有向图G。（1）图G中无环令DI表示从顶点0到顶点I的最长路径长度。对于图中每条从点I指向点J的权为CI

35、,J的边，有性质DI+CI,J0)And(MapK,B0)Thenn如果A与K，K与B均可达nIF(MapA,B=0)Or(MapA,BMapA,K+MapK,B)Thenn 如果A、B不可达，或者A、B之间的路径不如A-K-B这条路径短，则改变MapA,B的值nMapA,B:=MapA,K+MapK,B;n注：MapA,B为从A到B的最短路的距离，如果A,B不可达，则MapA,B=0。n在求改进M条边使最短路下降最快中，我们同样可以发现：n 1：将道路：将道路A-B改造改造M条边可以分为如下两个问题（如果条边可以分为如下两个问题（如果K是最短是最短路上的一点）路上的一点）n 一：求一：求A-

36、K改造改造T条边；条边；二：求二：求K-B改造改造M-T条边。条边。nT可以取从可以取从0至至M的任意值。问题的任意值。问题A-B改造改造M条边的最优解取决与条边的最优解取决与这两个子问题的最优解。这两个子问题的最优解。n 2：在求：在求M条边的过程中，始终只与改造条边的过程中，始终只与改造T与与M-T条边的问题发生条边的问题发生联系。联系。nn以上两个特点即为“动态规划”的“无后效性”与“最优子问题”两个性质。所以，这个“城市交通”问题的算法为“动态规划”算法。n设MapA,B,M的值为从A到B且改造M条边的最短路长度，则：n MapA,B,M=MinMapA,K,T+MapK,B,M-Tn

37、 其中其中T为从为从0到到M中的一个数，中的一个数，K为为A到到B中中间的一点间的一点。n这个问题在确定K是与Floyd算法相同，所以这个问题实质上是一个“双重动态规划”问题。具体算法如下：nForG:=1ToMDo分M个阶段来解这个问题nnForK:=1ToNDonForI:=1ToNDonForJ:=1ToNDoFloyd算法nBeginnForT:=0ToGDonIfMapI,K,T+MapK,J,G-TMapI,J,GThennMapI,J,G:=MapI,K,T+MapK,J,G-T;nEnd;n说明：这个问题的Map数组的初始值与上一个Floyd算法不一样，初始值均为MaxInt。

38、算法的时间复杂度为O(N3*M2)，约为O(N5)，还是一个多项式级的算法。公路通行税n在在PALMIA国家内，有国家内，有N个城市由公路相连（每条公路个城市由公路相连（每条公路恰好双向连接两个城市）。经由一条公路或多条公路，恰好双向连接两个城市）。经由一条公路或多条公路，从任一城市出发可以到达其余各个城市。直到今年，公从任一城市出发可以到达其余各个城市。直到今年，公路上才要征收公路通行税。在每条公路的中间，有一征路上才要征收公路通行税。在每条公路的中间，有一征税员，从每一辆经由此路的车收取税员，从每一辆经由此路的车收取 1 PALMIA COIN（1PC）。）。n政府官员决定减少收税员而推行

39、公路印花。如果一辆车政府官员决定减少收税员而推行公路印花。如果一辆车欲进入一条公路，就必须将这张印花贴在窗上。政府官欲进入一条公路，就必须将这张印花贴在窗上。政府官员决定：一年的公路印花的价值相当于在两个最远城市员决定：一年的公路印花的价值相当于在两个最远城市之间进行之间进行100次旅行所需的费用。两个城市之间的距离次旅行所需的费用。两个城市之间的距离是从一个城市到达第二个城市所需经过的最少数目的公是从一个城市到达第二个城市所需经过的最少数目的公路数。你的任务是编写一个程序计算出公路印花的价值。路数。你的任务是编写一个程序计算出公路印花的价值。分析n看了题目，觉得这是一道最短路的题目，我们可以

40、枚举N个城市，每次用单源最短路求出从当前枚举的城市到各城市间的最短路，所有最短路的值之中最大的乘以100即为问题的解。n因为n最大可以达到1000，而图中的道路总数不超过2000，所以我们在存储图的时候要用邻接表而不是邻接矩阵。如果直接套用经典的Dijkstra算法，整个算法的时间复杂度将会达到o(n3)，根本不可能在规定时限内出解。n注意到整个图虽然最多有注意到整个图虽然最多有1000个点，但由于它的总边数不个点，但由于它的总边数不会超过会超过2000，我们用的又是邻接表，如果可以将，我们用的又是邻接表，如果可以将Dijkstra过程中找最佳点的循环优化或是去掉，过程中找最佳点的循环优化或是

41、去掉，Dijkstra算法的时算法的时间复杂度将会降到接近于间复杂度将会降到接近于o(n+m)。n我们可以采用堆排序的方法来解决这一问题，由于第二重我们可以采用堆排序的方法来解决这一问题，由于第二重循环每更新一个最短路的值就要修改该点在堆中的位置，循环每更新一个最短路的值就要修改该点在堆中的位置，修该的最多次数为图的边数，所以修该的最多次数为图的边数，所以Dijkstra算法的时间复算法的时间复杂度可以降为杂度可以降为o(n+m*logn)，整个算法的时间复杂度降为，整个算法的时间复杂度降为o(n*(n+m*logn)，在最坏的情况下要循环，在最坏的情况下要循环1000*(1000+2000*log1000)21000000次。次。Bfs求解n首先这一题的道路数就不超过2000，远小于n2，这是它的一大不同之处。其实在一开始我们就忽略了一个重要的条件：所有边的长度都固定为1。这是这道题目与一般最短路问题最大的不同之处。因为所有道路的长度固定为1，所以我们可以用广搜来做这道题，广搜的算法也很容易想到。由于广搜是先进先出，我们无须选择当前最优点来更新最短路的值，所以用广搜求从一个点到其余各点的最短路时间复杂度仅为o(n+m)，这样一来，整个算法的时间复杂度为o(n*(n+m)，最坏时为1000*(1000+2000)=3000000，可以很快地通过所有数据。