图论的基本算法及应用课件.ppt

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

1、图论的基本算法及其应用长沙市雅礼中学长沙市雅礼中学 朱全民朱全民NOIP若干图论的考题Core(2007)Core(2007):图的多源最短路算法及其简单图的多源最短路算法及其简单处理处理双栈排序双栈排序(2008):栈的应用栈的应用+二分图的搜索二分图的搜索最优贸易最优贸易(2009)(2009):基本图论基本图论关于图论的基本问题图的基本概念及其存储结构（邻接矩阵和邻接表）图的基本概念及其存储结构（邻接矩阵和邻接表）图的遍历（深度优先和宽度优先遍历）图的遍历（深度优先和宽度优先遍历）图的连通性问题（求连通分量和强连通分量，关键节点）图的连通性问题（求连通分量和强连通分量，关键节点）有向无环

2、图的拓扑序列有向无环图的拓扑序列特殊图（偶图和一笔画问题、二分图和匹配问题）特殊图（偶图和一笔画问题、二分图和匹配问题）图的最小生成树及其应用图的最小生成树及其应用图的最短路问题图的最短路问题单源最短路（单源最短路（DIJKSTRADIJKSTRA算法，算法，BELLMANBELLMAN算法，算法，SPFASPFA算法）算法）任意两点的最短路（任意两点的最短路（FLOYDFLOYD算法）算法）一个简单问题一摆渡人欲将一只狼一摆渡人欲将一只狼,一头羊一头羊,一篮菜从河一篮菜从河西渡过河到河东西渡过河到河东.由于船小由于船小,一次只能带一一次只能带一物过河，并且狼与羊物过河，并且狼与羊,羊与菜不能

3、独处羊与菜不能独处.给出渡河方法给出渡河方法.解解：用四维：用四维0-10-1向量表示向量表示(人人,狼狼,羊羊,菜菜)在河西岸的在河西岸的状态状态(在河西岸则分量取在河西岸则分量取1,1,否则取否则取0),0),共有共有24=16 种状态种状态.在河东岸的状态类似记作在河东岸的状态类似记作.由题设由题设,状态状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许是不允许的的,从而对应状态从而对应状态(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不也是不允许的允许的.以可以可允许的允许的10个个状态状态向量作为顶点向量作为顶点,将可能互相转将可能互相转移的状态用

4、线段连接起来构成一个图移的状态用线段连接起来构成一个图.根据此图便可找到根据此图便可找到渡河方法渡河方法.(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)(1,0,1,0)(1,0,1,1)(1,1,0,1)(1,1,1,0)(1,1,1,1)河西河西=(=(人人,狼狼,羊羊,菜菜)河东河东=(=(人人,狼狼,羊羊,菜菜)将将10个顶点分别记为个顶点分别记为A1,A2,A10

5、,则则渡河问题化为在该渡河问题化为在该图中求一条从图中求一条从A1到到A10的路的路.从图中易得到两条路：从图中易得到两条路：A1 A6 A3 A7 A2 A8 A5 A10;A1 A6 A3 A9 A4 A8 A5 A10.图的矩阵表示图的矩阵表示 邻接表邻接表12345623413513623634512456拓扑排序拓扑排序 按照有向图给出的次序关系，将图中顶点排成一个按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序可以人为加上任意的次序关系。由此所

6、得顶点的线性序列称之为拓扑有序序列列称之为拓扑有序序列例如：对于有向图例如：对于有向图BDAC可求得拓扑有序序列可求得拓扑有序序列：A B C D 或或 A C B D问题：求网线线序问题：求网线线序网线从机房连接到办公室在机房，所有网线从左到右编号为1,2,3,N 给出每两条线是否交叉的信息，请计算办公室内从左到右各条线的编号 大数指向小数 由小到大做拓扑排序欧拉道路和回路经过每条边一次且仅一次经过每条边一次且仅一次先看回路先看回路必要条件：所有点度为偶数必要条件：所有点度为偶数充分条件：还是充分条件：还是“所有点度为偶数所有点度为偶数”证明！证明！把欧拉回路构造出来把欧拉回路构造出来“圈套

7、圈圈套圈”可能套不出来吗？想一想可能套不出来吗？想一想幼儿园的粉刷幼儿园里有很多房屋幼儿园里有很多房屋房屋与房屋之间连以走廊房屋与房屋之间连以走廊走廊与房屋之间有一扇门走廊与房屋之间有一扇门幼儿园长想把门漆成绿色或者黄色，使得幼儿园长想把门漆成绿色或者黄色，使得任意一条走廊两头门的颜色不同任意一条走廊两头门的颜色不同任意一间房屋上的门，绿色门的数量与黄色门的数量相差不超任意一间房屋上的门，绿色门的数量与黄色门的数量相差不超过过1 1。如何实现？如何实现？每个房屋的门都是偶数个每个房屋的门都是偶数个把奇数改造成偶数！把奇数改造成偶数！最小生成树问题求一个连通子图，使得边权和最小求一个连通子图，使

8、得边权和最小Prim算法任意时刻的中间结果都是一棵树任意时刻的中间结果都是一棵树从一个点开始从一个点开始每次都花最小的代价，用一条加进一个新点每次都花最小的代价，用一条加进一个新点问题：问题：这样做是对的吗？这样做是对的吗？如何快速找到这个如何快速找到这个“最小代价最小代价”？堆！堆！Prim算法框架初始化，树仅含一个任意一点v0把v0的邻边插入堆for i:=1 to n-1 dobegin 从堆中取出最小值，设边为(u,v)，v为新点 (u,v)加入生成树中 v和它所有不在树中的邻居组成的边插入堆end;每次取最小值为O(logm)总时间复杂度为O(nlogm)Kruskal算法任意时刻的

9、中间结果是一个森林任意时刻的中间结果是一个森林从从n n个点的集合开始个点的集合开始每次选不产生圈的前提下权最小的边加入每次选不产生圈的前提下权最小的边加入问题：问题：这样做是对的吗？这样做是对的吗？如何快速的判断是否产生圈如何快速的判断是否产生圈并查集并查集Kruskal算法框架把所有边按照权值从小到大排序为把所有边按照权值从小到大排序为e e1 1,e,e2 2,初始化初始化n n个集合，个集合，S Si i=i=isize:=0;size:=0;for i:=1 to m dofor i:=1 to m do if e if ei i的两个端点的两个端点u,vu,v不在同一个集合不在同一

10、个集合 thenthen begin begin 合并合并S Su u和和S Sv v inc(size);inc(size);if size=n 1 then break;if size=n 1 then break;end;end;最坏情况循环执行最坏情况循环执行m m次，判断约次，判断约O(1)O(1)如果输入已经排序好，则总时间复杂度为如果输入已经排序好，则总时间复杂度为O(mO(m)，否则为，否则为O(mlogmO(mlogm)SSSP(Dijkstra算法)核心思想：按路径递增的次序产生最短路径的算核心思想：按路径递增的次序产生最短路径的算法法 1)1)找到图中最短的路径，设为（找

11、到图中最短的路径，设为（v,vv,vj j）,将将j j设为设为已标号的点已标号的点 2)2)找下一条次短的路径，假设终点为找下一条次短的路径，假设终点为k,k,将将k k设为已设为已标号的点标号的点,那么要么是（那么要么是（v,vv,vk k）要么是（）要么是（v,vv,vj j,v,vk k）,若经过若经过v vj j,将将j j设为已检查的点设为已检查的点,放入集合放入集合.3)3)以次短路径出发找第三短的路径以次短路径出发找第三短的路径,类似第二步的类似第二步的方法方法.4)4)按上述方法一直到所有的顶点被检查过按上述方法一直到所有的顶点被检查过,则从则从v v到到其他顶点的最短路径求

12、出其他顶点的最短路径求出.DijkstraDijkstra算法算法令d(u)=mindv+w(v,u)|v存在，设 中最小的元素为i，则令（即求出了i的最短路长度），并根据di来对 进行更新。每次求出一个d值，重复n次就可以得到所有点的最短路径长度。下面是Dijkstra算法的伪代码：Proc SSSP_Dijkstra(start:integer);For i:=1 to n do d(i):=;d(start):=0;For k:=1 To n Do【i:=GetMin(ProcSSSP_Dijkstra(start:integer);Fori:=1tondod(i):=;d(start)

13、:=0;Fork:=1TonDo【i:=GetMin();取出d中值最小的结点idi:=d(i);Delete(i,d);令di等于d(i)，并将i从d中删除Foreachnodeuexistedge(i,u)【对每条从i连出的边进行检查Ifd(u)du+w(u,v)then/松弛判断dv=du+w(u,v)/松弛操作2阶段结束foreachedge（u,v）E(G)doIfdvdu+w(u,v)thenExitfalseExittrueSPFA(Shortest Path Faster Algorithm)SPFASPFA对对Bellman-FordBellman-Ford算法优化的关键之处

14、在于意识到：只算法优化的关键之处在于意识到：只有那些在前一遍松弛中改变了距离估计值的点，才可能引有那些在前一遍松弛中改变了距离估计值的点，才可能引起他们的邻接点的距离估计值的改变。因此，用一个先进起他们的邻接点的距离估计值的改变。因此，用一个先进先出的队列来存放被成功松弛的顶点。初始时，源点先出的队列来存放被成功松弛的顶点。初始时，源点s s入入队。当队列不为空时，取出对首顶点，对它的邻接点进行队。当队列不为空时，取出对首顶点，对它的邻接点进行松弛。如果某个邻接点松弛成功，且该邻接点不在队列中，松弛。如果某个邻接点松弛成功，且该邻接点不在队列中，则将其入队。经过有限次的松弛操作后，队列将为空，

15、算则将其入队。经过有限次的松弛操作后，队列将为空，算法结束。法结束。SPFASPFA算法的实现，需要用到一个先进先出的队列算法的实现，需要用到一个先进先出的队列 queue queue 和一个指示顶点是否在队列中的和一个指示顶点是否在队列中的 标记数组标记数组 markmark。SPFA算法 设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点首结点u，并且用，并且用u点当前的最短路径估计值对离开点当前的最短路径估计值对离开u点所指向的结点点所指向的结点v进行松弛操作，如果进行松弛操作，如果v点的最短路径估计值有所调整，

16、且点的最短路径估计值有所调整，且v点不在当前点不在当前的队列中，就将的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。操作，直至队列空为止。SPFA(G,w,s)1.INITIALIZE-SINGLE-SOURCE(G,s)2.INITIALIZE-QUEUE(Q)3.ENQUEUE(Q,s)4.While Not EMPTY(Q)5.Do u DLQUEUE(Q)6.For 每条边每条边(u,v)EG7.Do tmp dv8.Relax(u,v,w)9.If(dv tmp)and(v不在不在Q中中)10.ENQU

17、EUE(Q,v)我们用数组我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：。我们采取的方法是动态逼近法：floyd-warshallfloyd-warshall算法算法设设d d i i，j j，k k 是是在只允许经过结点在只允许经过结点11k k 的情况下的情况下i i到到j j的最短路长度的最短路长度则它有两种情况（想一想，为什么）：则它有两种情况（想一想，为什么）：如果最短路经过点如果最短路经过点k k，那么，那么d d i i，j j，k k 应该等于应该等于d d i i，k k，k k

18、-1+-1+d d k k，j j，k k-1-1；如果最短路不经过点如果最短路不经过点k k，那么，那么d d i i，j j，k k 应该等于应该等于d d i i，j j，k k-1-1。综合起来综合起来d d i i，j j，k k=min=mind d i i，k k，k k-1+-1+d d k k，j j，k k-1-1，d d i i，j j，k k-11边界条件是边界条件是d d i i，j j，0=0=w w(i i，j j)（不存在的边权为（不存在的边权为）floyd-warshall算法基本的动态规划把k放外层循环，可以节省内存对于每个k，计算每两点的目前最短路for

19、k:=1 to n dofor i:=1 to n do for j:=1 to n do if(di,k)and(dk,j)and(di,k+dk,jdi,j)then di,j:=di,k+dk,j一定要背下来！时间复杂度：O(n3)用途：预处理！选址问题选址问题 现准备在现准备在 n n 个居民点个居民点v v1 1,v v2 2,v vn n中设中设置一银行置一银行.问设在哪个点问设在哪个点,可使最大服务距可使最大服务距离最小离最小?若设置两个银行若设置两个银行,问设在哪两个点问设在哪两个点?模型假设模型假设 假设各个居民点都有条件设置假设各个居民点都有条件设置银行银行,并有路相连并有

20、路相连,且路长已知且路长已知.模型建立与求解模型建立与求解用用FloydFloyd算法求出任意两个居民点算法求出任意两个居民点v vi i,v vj j 之间的最短距离之间的最短距离,并用并用d dij ij 表示表示.设置一个银行设置一个银行,银行设在银行设在 v vi i 点的最大服务距离为点的最大服务距离为求求k,使使 即若设置一个银行即若设置一个银行,则银行设在则银行设在 vk 点点,可使最大服务距离最小可使最大服务距离最小.设置两个银行设置两个银行,假设银行设假设银行设在在vs,vt 点点使最大服务距离最小使最大服务距离最小.记记则则s,t 满足：满足：进一步进一步,若设置多个银行呢

21、？若设置多个银行呢？求求k,使使 即若设置一个银行即若设置一个银行,则银行设在则银行设在 vk 点点,可使最可使最大服务距离最小大服务距离最小.设置两个银行设置两个银行,假设银行设假设银行设在在vs,vt 点点使最使最大服务距离最小大服务距离最小.记记则则s,t 满足：满足：进一步进一步,若设置多个银行呢？若设置多个银行呢？最优贸易最优贸易某国有某国有M M个城市个城市N N条道路，任意两个城市有道路，有一部分条道路，任意两个城市有道路，有一部分道路为单行线，一部分为双向道路。道路为单行线，一部分为双向道路。某人去该国旅游，从城市某人去该国旅游，从城市1 1出发到城市出发到城市n n结束，他想

22、做水晶结束，他想做水晶球的生意一次挣点旅行费用，每个城市有一个水晶球的价球的生意一次挣点旅行费用，每个城市有一个水晶球的价格（买入卖出都一样），他可以经过每个城市多次。格（买入卖出都一样），他可以经过每个城市多次。问他能挣最多的费用为多少？问他能挣最多的费用为多少？如下图，假设城市如下图，假设城市1515的价格为的价格为4 4，3 3，5 5，6 6，1 1则选择则选择1-4-5-4-51-4-5-4-5路线，路线，挣得挣得5 5分析这是一道非常典型的图论题这是一道非常典型的图论题,如果有扎实的图论基础解决如果有扎实的图论基础解决起来并不困难起来并不困难.解决这道题的关键是发现解决这道题的关键

23、是发现,我们可以将原图中的任意一个我们可以将原图中的任意一个强连通分量收缩为一个点强连通分量收缩为一个点,这个新点的买入价格等于该强这个新点的买入价格等于该强连通分量中最小的买入价格连通分量中最小的买入价格,这个新点的卖出价格等于该这个新点的卖出价格等于该强连通分量中最大的卖出价格强连通分量中最大的卖出价格.这是因为这是因为,这个新点的性这个新点的性质和一个强连通分量是一样的质和一个强连通分量是一样的,如果我们要在一个强连通如果我们要在一个强连通分量中进行购买操作分量中进行购买操作,一定会选择买入价格最小的那个点一定会选择买入价格最小的那个点,如果我们要在一个强连通分量中进行卖出操作如果我们要

24、在一个强连通分量中进行卖出操作,也一定会也一定会选择卖出价格最大的那个点选择卖出价格最大的那个点.分析所以算法就非常清晰了所以算法就非常清晰了.首先利用首先利用DFSDFS将所有的强连通分将所有的强连通分量收缩量收缩,这样我们就可以得到一个有向无环图这样我们就可以得到一个有向无环图G.G.由于由于G G中中没有环没有环,我们可以对我们可以对G G进行拓扑排序进行拓扑排序,然后利用递推求得然后利用递推求得到达某个点到达某个点i i时时,可能的最低买入价格可能的最低买入价格best(i)best(i)是多少是多少,以以及该点最终能否到达终点及该点最终能否到达终点.最后对于所有能够到达终点的最后对于

25、所有能够到达终点的点点p,p,设其卖出价格为设其卖出价格为sell(p),sell(p),在在sell(p)-best(p)sell(p)-best(p)中取中取最大值即得到答案最大值即得到答案.时间复杂度仅为时间复杂度仅为O(V+E).O(V+E).在实现的时候最好使用栈消除在实现的时候最好使用栈消除DFSDFS中的递归调用中的递归调用,因为图因为图中的点可以达到中的点可以达到100000,100000,当递归深度达到这么大的时候有当递归深度达到这么大的时候有相当大的几率发生栈溢出相当大的几率发生栈溢出.参考实现中采用了非递归实现参考实现中采用了非递归实现DFS.DFS.奇怪的电梯奇怪的电梯

26、大楼的每一层楼都可以停电梯，而且第大楼的每一层楼都可以停电梯，而且第i i层楼层楼(1=i=N)(1=i=N)上上有一个数字有一个数字Ki(0=Ki=N)Ki(0=Ki=N)。电梯只有四个按钮：开，关，。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 3 3 1 2 52 5代表了代表了Ki(K1=3,K2=3,)Ki(K1=3,K2=3,)，从一楼开始。在一楼，从一楼开始。在一楼，按按“上上”可以到可以到4 4楼，按

27、楼，按“下下”是不起作用的，因为没有是不起作用的，因为没有-2 2楼。那么，从楼。那么，从A A楼到楼到B B楼至少要按几次按钮呢？楼至少要按几次按钮呢？输入：输入：二行，第一行为三个用空格隔开的正整数，表示二行，第一行为三个用空格隔开的正整数，表示N,A,B(1N200,1A,BN)N,A,B(1N200,1A,BN)，第二行为，第二行为N N个用空格隔开个用空格隔开的正整数，表示的正整数，表示KiKi。输出：仅一行，即最少按键次数输出：仅一行，即最少按键次数,若无法到达，则输出若无法到达，则输出-1-1。构图LIFT.INLIFT.IN5 1 55 1 53 3 1 2 53 3 1 2

28、5LIFT.OUTLIFT.OUT3 3对于对于A A楼而言，实际上对它最多只能做楼而言，实际上对它最多只能做2 2个操作，上到个操作，上到A+XA+X层或下到层或下到A-XA-X层，当然前提是存在层，当然前提是存在A+XA+X或或A-XA-X层。显然，如层。显然，如果把每一层楼看做一个顶点，如果果把每一层楼看做一个顶点，如果A A楼可以到楼可以到B B楼，则从顶楼，则从顶点点A A引一条到顶点引一条到顶点B B的边，这样一来，问题就变成了图论中的边，这样一来，问题就变成了图论中的两顶点间最短路径问题了！当然权设为的两顶点间最短路径问题了！当然权设为1 1就行了。就行了。人穿柱子游戏人穿柱子游

29、戏在一个无限长的条形路上，有n(n=200)个柱子，体积不计，有一个人想从左边走到右边，人近似看成一个半径为R的圆（如下图），问能否实现？构图每个圆的大小完全相同，不存在包含，相切（如每个圆的大小完全相同，不存在包含，相切（如果内切，就是重合了，如果外切，就是中间不连果内切，就是重合了，如果外切，就是中间不连通的）等等复杂的关系，只有相交和相离的关系，通的）等等复杂的关系，只有相交和相离的关系，而且如果而且如果2 2个圆之间相交的话，那么这个圆之间相交的话，那么这2 2个圆就是个圆就是相通的，可以在这相通的，可以在这2 2个圆的圆心之间连一条边，增个圆的圆心之间连一条边，增加一个源点，与上边有

30、交点的圆和源点连一条边，加一个源点，与上边有交点的圆和源点连一条边，增加一个汇点，与下边有交点的圆和汇点连一条增加一个汇点，与下边有交点的圆和汇点连一条边，这样就把一道几何题完全转换成了一道图论边，这样就把一道几何题完全转换成了一道图论题，只要判断源点和汇点之间是否有路就可以了题，只要判断源点和汇点之间是否有路就可以了奇怪的数列奇怪的数列编程输入编程输入3 3个整数个整数n n，p p，q q，寻找一个由整数组成的，寻找一个由整数组成的数列（数列（a a1 1，a a2 2，a an n），要求：其中任意连续），要求：其中任意连续p p项之和为正数，任意连续项之和为正数，任意连续q q项之和为

31、负数。项之和为负数。0n1000n100，0p0p，qnqn，若不存在这样的整数数列，则输出，若不存在这样的整数数列，则输出NONO；否则输出满足条件的一个数列即可。；否则输出满足条件的一个数列即可。输入格式：输入格式：仅一行分别表示仅一行分别表示n n，p p，q q，之间用一个空格隔开。，之间用一个空格隔开。输出格式：输出格式：只有一行，有解即输出这个数列，每个数之间用一只有一行，有解即输出这个数列，每个数之间用一个空格隔开。否则输出个空格隔开。否则输出NONO。分析如果我们按常规思想，直接将第如果我们按常规思想，直接将第i i个整数个整数a ai i开始的开始的k k个整数个整数之和描述

32、成多项式之和描述成多项式a ai i+a+ai+1i+1+a+ai+k-1i+k-1的话，问题就很难再往的话，问题就很难再往下思考和解决了。所以，我们不防换个角度，暂且撇去每下思考和解决了。所以，我们不防换个角度，暂且撇去每一项数究竟为何值的具体细节，而将注意力集中至连续性一项数究竟为何值的具体细节，而将注意力集中至连续性这一特点上。设这一特点上。设s si i表示数列前表示数列前i i个整数之和，即个整数之和，即s si i=a=a1 1+a+a2 2+a+ai i。其中。其中s s0 0=0(0=0(0i in)n)。显然根据题意，有：。显然根据题意，有：s si issi+pi+p (0

33、 (0i in-p)n-p)s si+qi+qsssj j(0(0i i，j jn)n)，则从，则从s si i往往s sj j引出引出一条有向边。一条有向边。构图对于n=6，p=5，q=3的情况，我们可以建立下图：对图进行拓扑排序；对图进行拓扑排序；if if 图有回路图有回路 then then 无解退出无解退出 else else 生成拓扑序列生成拓扑序列order0ordernorder0ordern；那么如果得到了一个拓扑序列，该如何转换成那么如果得到了一个拓扑序列，该如何转换成s s数组呢？因为拓扑序列数组呢？因为拓扑序列中顶点对应的中顶点对应的s s值是递减的，其中值是递减的，其

34、中s s0 0=0=0。如果如果orderi=0orderi=0，则依次设定，则依次设定s sorder0order0=i=i，s sorder1order1=i-1=i-1，s sorderi-orderi-11=1=1，s sorderiorderi=0=0，s sorderi+1orderi+1=-1=-1，s sordernordern=i-n=i-n。例如，对于上图所示的有向图，可以得到下表：例如，对于上图所示的有向图，可以得到下表：所以，得到所以，得到s s0 0=0=0，s s1 1=-3=-3，s s2 2=2=2，s s3 3=-1=-1，s s4 4=-4=-4，s s5

35、5=1=1，s s6 6=-2=-2。再根据。再根据s s的定义，由：的定义，由：a ai i=(a=(a0 0+a+a1 1+a+ai-1i-1+a+ai i)-(a)-(a0 0+a+a1 1+a ai-1i-1)=s)=si i-s-si-1i-1 ，求出：，求出：a a1 1=s=s1 1-s-s0 0=-3=-3，a a2 2=s=s2 2-s-s1 1=5=5，a a3 3=s=s3 3-s-s2 2=-3=-3，a a4 4=s=s4 4-s-s3 3=-3=-3，a a5 5=s=s5 5-s s4 4=5=5，a a6 6=s=s6 6-s-s5 5=-3=-3。显然这个整数

36、数列的任意连续个整数之和为正，。显然这个整数数列的任意连续个整数之和为正，任意连续个整数之和为负。任意连续个整数之和为负。牧场规划牧场规划小可可的好朋友小可可的好朋友SealockSealock最喜欢吃花生了，于是借用了最喜欢吃花生了，于是借用了小可可的牧场从事花生选种试验。他以网格的方式，非小可可的牧场从事花生选种试验。他以网格的方式，非常规整地把牧场分割成常规整地把牧场分割成M*NM*N个矩形区域个矩形区域(M*N(M*N5000)5000)，由，由于各个区域中地水面、沼泽面积各不相同，因此各区域于各个区域中地水面、沼泽面积各不相同，因此各区域地实际可种植面积也各不相同，已知区域地实际可种

37、植面积也各不相同，已知区域(i,j)(i,j)地可种地可种面积使面积使A(i,j)A(i,j)。每个区域种最多只能种植一个品种地花生。可种植面积每个区域种最多只能种植一个品种地花生。可种植面积为零地区域不能被选择用来从事选种试验，同时为了防为零地区域不能被选择用来从事选种试验，同时为了防止花粉传播到相邻区域造成试验结果不正确，任何两个止花粉传播到相邻区域造成试验结果不正确，任何两个相邻的区域都不可以同时种植花生。这里说的相邻指的相邻的区域都不可以同时种植花生。这里说的相邻指的是两个区域有公共边，仅仅有公共点的两个区域不算做是两个区域有公共边，仅仅有公共点的两个区域不算做相邻。相邻。小可可准备帮

38、助小可可准备帮助SealockSealock规划一下如何选择种植区域，规划一下如何选择种植区域，才能使得实际可种植面积总和最大。才能使得实际可种植面积总和最大。构图将试验田转化为点、并连接相邻的试验田后可以发现，我们得到的是将试验田转化为点、并连接相邻的试验田后可以发现，我们得到的是一个二分图。通过对原图的黑白染色，可以把其中的一部分称为白点、一个二分图。通过对原图的黑白染色，可以把其中的一部分称为白点、另一部分称为黑点。由二分图建立网络：加入源点和汇点，从源点向另一部分称为黑点。由二分图建立网络：加入源点和汇点，从源点向每个白点引一条边，容量为白点对应试验田的面积；从每个黑点向汇每个白点引一

39、条边，容量为白点对应试验田的面积；从每个黑点向汇点引边，容量为该黑点的对应面积。最后将相邻点之间的边改为网络点引边，容量为该黑点的对应面积。最后将相邻点之间的边改为网络中的边，由白点指向黑点，容量为正无穷。通过求网络最大流得到它中的边，由白点指向黑点，容量为正无穷。通过求网络最大流得到它的最小割，即为最优方案。的最小割，即为最优方案。S T图图1 建立网建立网络络瘦陀陀和胖陀陀瘦陀陀和胖陀陀一场可怕的战争后，瘦陀陀和他的好朋友胖陀陀一场可怕的战争后，瘦陀陀和他的好朋友胖陀陀将要凯旋。将要凯旋。瘦陀陀处在城市瘦陀陀处在城市A A胖陀陀处在另外一个未知的城市胖陀陀处在另外一个未知的城市他们打算选一

40、个城市他们打算选一个城市X X（这个由瘦陀陀来决定）（这个由瘦陀陀来决定）胖陀陀会赶在瘦陀陀之前到达城市胖陀陀会赶在瘦陀陀之前到达城市X X然后等待瘦陀陀也赶到城市然后等待瘦陀陀也赶到城市X X与他汇合，并举办一次庆与他汇合，并举办一次庆祝宴会（由瘦陀陀请客）祝宴会（由瘦陀陀请客）接着一起回到他们的家乡城市接着一起回到他们的家乡城市B B由于胖陀陀嘴馋，他要求举办宴会的城市必须是瘦陀由于胖陀陀嘴馋，他要求举办宴会的城市必须是瘦陀陀回家的路线中举办宴会最贵的一个城市。陀回家的路线中举办宴会最贵的一个城市。一个例子（续）瘦陀陀正专注地看回家的地图瘦陀陀正专注地看回家的地图地图上标有地图上标有n（n

41、200）个城市）个城市和某些城市间直达的道路和某些城市间直达的道路以及每条道路的过路费以及每条道路的过路费瘦陀陀还知道在每一座城市举瘦陀陀还知道在每一座城市举办宴会的花费。办宴会的花费。给出地图和给出地图和A、B的位置的位置请你告诉瘦陀陀回家的最小费请你告诉瘦陀陀回家的最小费用用你的程序会接收到多次询问你的程序会接收到多次询问即对于每对城市即对于每对城市(c1,c2)，你的，你的程序应该立刻给出瘦陀陀从程序应该立刻给出瘦陀陀从c1到到c2的最小花费。的最小花费。分析胖陀陀规定必须在最贵的城市举办宴会胖陀陀规定必须在最贵的城市举办宴会因此不能简单地选择一条最短路走因此不能简单地选择一条最短路走若

42、路上有一个花费特别贵的城市若路上有一个花费特别贵的城市对于每个点对于每个点X X，如果在那里办宴会，如果在那里办宴会如何求最短路？如何求最短路？多个询问怎么处理？多个询问怎么处理？floydfloyd计算每两点的距离？计算每两点的距离？SSSPSSSP就可以胜任吗？就可以胜任吗？AB=AX+XBAB=AX+XB树网的核树网的核 给出一棵无根树，边上有权。称树的最长路径为直径，定义路径的偏心距为：点到路径的上的点的最小值的最大值，给出一个s，找出直径上的某段长度不超过s的路径，使得偏心距最小。分析考虑到树的性质，对于任意两点，最短路考虑到树的性质，对于任意两点，最短路=联通路联通路=最长最长路。

43、路。首先用首先用floydfloyd算法求出任意两点之间最短路。同时可以求算法求出任意两点之间最短路。同时可以求出最长路径上都有哪些点。由于这是一棵树，最短路必出最长路径上都有哪些点。由于这是一棵树，最短路必然唯一。设然唯一。设mida,bmida,b是是a,ba,b之间的联通路上的一个中间点。之间的联通路上的一个中间点。考虑问题的解，构造一个函数考虑问题的解，构造一个函数F(k,a,b)F(k,a,b)为为K K到到abab间的最短间的最短路的长度。则路的长度。则f(k,a,b)=mindk,mida,b,fk,a,mida,b,fk,midf(k,a,b)=mindk,mida,b,fk,

44、a,mida,b,fk,mida,b,ba,b,b写出了这个方程，便不难得出一个三次方的算法。在写出了这个方程，便不难得出一个三次方的算法。在实际做的时候，可以把实际做的时候，可以把k k放在最外层枚举，这样内层实际放在最外层枚举，这样内层实际上只用到了上只用到了f f的后面的后面2 2维，用维，用2 2维数组记录即可。维数组记录即可。双栈排序双栈排序 有两个队列和两个栈有两个队列和两个栈,分别命名为队列分别命名为队列1(q),1(q),队列队列2(q2),2(q2),栈栈1(s1)1(s1)和栈和栈2(s2).2(s2).最初的时候最初的时候,q2,s1,q2,s1和和s2s2都都为空为空,

45、而而q q中有中有n n个数个数(n=1000),(n=1000),为为1n1n的某个排列的某个排列.现在支持如下四种操作现在支持如下四种操作:a a操作操作,将将 q q的首元素提取出并加入的首元素提取出并加入s1s1的栈顶的栈顶.b b操作操作,将将s1s1的栈顶元素弹出并加入的栈顶元素弹出并加入q2q2的队列尾的队列尾.c c操作操作,将将 q q的首元素提取出并加入的首元素提取出并加入s2s2的栈顶的栈顶.d d操作操作,将将s2s2的栈顶元素弹出并加入的栈顶元素弹出并加入q2q2的队列尾的队列尾.请判断请判断,是否可以经过一系列操作之后是否可以经过一系列操作之后,使得使得q2q2中依

46、次中依次存储着存储着1,2,3,n.1,2,3,n.如果可以如果可以,求出字典序最小的一个求出字典序最小的一个操作序列操作序列.考虑单栈例1：1,2,3,4,5 例2：5,4,3,2,1 例3：3,2,4,5,1 例4：3,1,4,5,2 no;yes;yes;yes;定理定理：对于任意两个数定理：对于任意两个数qiqi和和qjqj来说来说,它们不能压入同它们不能压入同一个栈中的充要条件一个栈中的充要条件p p是是:存在一个存在一个k,k,使得使得ijkijk且且qkqiqj.qkqiq i,q jq i,这显然是不正确的这显然是不正确的.证明必要性：也就是必要性：也就是,如果两个数不可以压入

47、同一个栈如果两个数不可以压入同一个栈,那么它们那么它们一定满足条件一定满足条件p.p.这里我们来证明它的逆否命题这里我们来证明它的逆否命题,也就是也就是 如果如果不满足条件不满足条件p,p,那么这两个数一定可以压入同一个栈那么这两个数一定可以压入同一个栈.“.“不满足条件不满足条件p p有两种情况有两种情况:一种是对于任意一种是对于任意ijkijk且且qiqi;qiqi;另一种是对于任意另一种是对于任意iqj.iqj.第一种情况下第一种情况下,很显然很显然,在在qkqk被压入栈的时候被压入栈的时候,qi,qi已经被已经被弹出栈弹出栈.那么那么,qk,qk不会对不会对qjqj产生任何影响产生任何

48、影响(这里可能有点这里可能有点乱乱,因为看起来因为看起来,当当qjqKqjqK的时候的时候,是会有影响的是会有影响的,但实际但实际上上,这还需要另一个数这还需要另一个数R,R,满足满足JKRJKR且且 qrqjqk,qrqjqk,也就也就是证明充分性的时候所说的情况是证明充分性的时候所说的情况而事实上我们现在并不考而事实上我们现在并不考虑这个虑这个r,r,所以说所以说qkqk对对qjqj没有影响没有影响).).第二种情况下第二种情况下,我们可以发现这其实就是一个降序序列我们可以发现这其实就是一个降序序列,所以所以所有数字都可以压入同一个栈所有数字都可以压入同一个栈.这样这样,原命题的逆否命题得

49、证原命题的逆否命题得证,所以原命题得证所以原命题得证.此时此时,条件条件p p为为qiqi和和qjqj不能压入同一个栈的充要条件也得不能压入同一个栈的充要条件也得证证.构图构图这样这样,我们对所有的数对我们对所有的数对(i,j)(i,j)满足满足1=ij=n,1=ij=n,检检查是否存在查是否存在ijkijk满足满足qk q iq j.qk q iq j.如果存如果存在在,那么在点那么在点i i和点和点j j之间连一条无向边之间连一条无向边,表示表示q iq i和和qjqj不能压入同一个栈不能压入同一个栈.二分图的两部分看作两个栈二分图的两部分看作两个栈,因为二分图的同一部因为二分图的同一部分

50、内不会出现任何连边分内不会出现任何连边,也就相当于不能压入同一也就相当于不能压入同一个栈的所有结点都分到了两个栈中个栈的所有结点都分到了两个栈中.此时我们只考虑检查是否有解此时我们只考虑检查是否有解,所以只要所以只要O(n)O(n)检查检查出这个图是不是二分图出这个图是不是二分图,就可以得知是否有解就可以得知是否有解.深度优先搜索求解检查有解的问题已经解决检查有解的问题已经解决.接下来的问题是接下来的问题是,如何找到如何找到字典序最小的解字典序最小的解.实际上实际上,可以发现可以发现,如果把二分图染成如果把二分图染成1 1和和2 2两种颜色两种颜色,那么结点染色为那么结点染色为1 1对应当前结