图论的基本算法及应用精品文稿.ppt

图论的基本算法及应用第1页，本讲稿共60页NOIP若干图论的考题Core(2007)Core(2007):图的多源最短路算法及其简单图的多源最短路算法及其简单处理处理双栈排序双栈排序(2008):栈的应用栈的应用+二分图的搜索二分图的搜索最优贸易最优贸易(2009):基本图论基本图论第2页，本讲稿共60页关于图论的基本问题图的基本概念及其存储结构（邻接矩阵和邻接表）图的基本概念及其存储结构（邻接矩阵和邻接表）图的遍历（深度优先和宽度优先遍历）图的遍历（深度优先和宽度优先遍历）图的连通性问题（求连通分量和强连通分量，关键节点）图的连通性问题（求连通分量和强连通分量，关键节点）有向无环图的拓扑序列有向无环图的拓扑序列特殊图（偶图和一笔画问题、二分图和匹配问题）特殊图（偶图和一笔画问题、二分图和匹配问题）图的最小生成树及其应用图的最小生成树及其应用图的最短路问题图的最短路问题单源最短路（单源最短路（DIJKSTRA算法，算法，BELLMAN算法，算法，SPFA算法）算法）任意两点的最短路（任意两点的最短路（FLOYD算法）算法）第3页，本讲稿共60页一个简单问题一摆渡人欲将一只狼一摆渡人欲将一只狼,一头羊一头羊,一篮菜从河一篮菜从河西渡过河到河东西渡过河到河东.由于船小由于船小,一次只能带一一次只能带一物过河，并且狼与羊物过河，并且狼与羊,羊与菜不能独处羊与菜不能独处.给出渡河方法给出渡河方法.第4页，本讲稿共60页 解解：用四维：用四维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个个状态状态向量作为顶点向量作为顶点,将可能互相转移的将可能互相转移的状态用线段连接起来构成一个图状态用线段连接起来构成一个图.根据此图便可找到根据此图便可找到渡河方法渡河方法.第5页，本讲稿共60页(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,则则渡河问题化为在该图中求渡河问题化为在该图中求一条从一条从A1到到A10的路的路.从图中易得到两条路：从图中易得到两条路：A1 A6 A3 A7 A2 A8 A5 A10;A1 A6 A3 A9 A4 A8 A5 A10.第6页，本讲稿共60页图的矩阵表示图的矩阵表示 第7页，本讲稿共60页邻接表邻接表12345623413513623634512456第8页，本讲稿共60页拓扑排序拓扑排序 按照有向图给出的次序关系，将图中顶点排成一个线按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列称之为拓扑有序序列例如：对于有向图例如：对于有向图可求得拓扑有序序列可求得拓扑有序序列：A B C D 或或 A C B D第9页，本讲稿共60页问题：求网线线序问题：求网线线序网线从机房连接到办公室在机房，所有网线从左到右编号为1,2,3,N 给出每两条线是否交叉的信息，请计算办公室内从左到右各条线的编号 大数指向小数 由小到大做拓扑排序第10页，本讲稿共60页欧拉道路和回路经过每条边一次且仅一次经过每条边一次且仅一次先看回路先看回路必要条件：所有点度为偶数必要条件：所有点度为偶数充分条件：还是充分条件：还是“所有点度为偶数所有点度为偶数”证明！证明！把欧拉回路构造出来把欧拉回路构造出来“圈套圈圈套圈”可能套不出来吗？想一想可能套不出来吗？想一想第11页，本讲稿共60页幼儿园的粉刷幼儿园里有很多房屋幼儿园里有很多房屋房屋与房屋之间连以走廊房屋与房屋之间连以走廊走廊与房屋之间有一扇门走廊与房屋之间有一扇门幼儿园长想把门漆成绿色或者黄色，使得幼儿园长想把门漆成绿色或者黄色，使得任意一条走廊两头门的颜色不同任意一条走廊两头门的颜色不同任意一间房屋上的门，绿色门的数量与黄色门的数量相差不超过任意一间房屋上的门，绿色门的数量与黄色门的数量相差不超过1。如何实现？如何实现？每个房屋的门都是偶数个每个房屋的门都是偶数个把奇数改造成偶数！把奇数改造成偶数！第12页，本讲稿共60页最小生成树问题求一个连通子图，使得边权和最小求一个连通子图，使得边权和最小第13页，本讲稿共60页Prim算法任意时刻的中间结果都是一棵树任意时刻的中间结果都是一棵树从一个点开始从一个点开始每次都花最小的代价，用一条加进一个新点每次都花最小的代价，用一条加进一个新点问题：问题：这样做是对的吗？这样做是对的吗？如何快速找到这个如何快速找到这个“最小代价最小代价”？堆！堆！第14页，本讲稿共60页Prim算法框架初始化，树仅含一个任意一点v0把v0的邻边插入堆for i:=1 to n-1 dobegin 从堆中取出最小值，设边为(u,v)，v为新点 (u,v)加入生成树中 v和它所有不在树中的邻居组成的边插入堆end;每次取最小值为O(logm)总时间复杂度为O(nlogm)第15页，本讲稿共60页Kruskal算法任意时刻的中间结果是一个森林任意时刻的中间结果是一个森林从从n个点的集合开始个点的集合开始每次选不产生圈的前提下权最小的边加入每次选不产生圈的前提下权最小的边加入问题：问题：这样做是对的吗？这样做是对的吗？如何快速的判断是否产生圈如何快速的判断是否产生圈并查集并查集第16页，本讲稿共60页Kruskal算法框架把所有边按照权值从小到大排序为把所有边按照权值从小到大排序为e1,e2,初始化初始化n个集合，个集合，Si=isize:=0;fori:=1tomdoifei的两个端点的两个端点u,v不在同一个集合不在同一个集合thenbegin合并合并Su和和Svinc(size);ifsize=n1thenbreak;end;最坏情况循环执行最坏情况循环执行m次，判断约次，判断约O(1)如果输入已经排序好，则总时间复杂度为如果输入已经排序好，则总时间复杂度为O(m)，否则为，否则为O(mlogm)第17页，本讲稿共60页SSSP(Dijkstra算法)核心思想：按路径递增的次序产生最短路径的算法核心思想：按路径递增的次序产生最短路径的算法1)找到图中最短的路径，设为（找到图中最短的路径，设为（v,vj）,将将j设为已标号的点设为已标号的点2)找下一条次短的路径，假设终点为找下一条次短的路径，假设终点为k,将将k设为已标号的设为已标号的点点,那么要么是（那么要么是（v,vk）要么是（）要么是（v,vj,vk）,若经过若经过vj,将将j设设为已检查的点为已检查的点,放入集合放入集合.3)以次短路径出发找第三短的路径以次短路径出发找第三短的路径,类似第二步的方法类似第二步的方法.4)按上述方法一直到所有的顶点被检查过按上述方法一直到所有的顶点被检查过,则从则从v到其他顶到其他顶点的最短路径求出点的最短路径求出.第18页，本讲稿共60页Dijkstra算法算法令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):=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)thenExitfalseExittrue第21页，本讲稿共60页SPFA(Shortest Path Faster Algorithm)SPFA对对Bellman-Ford算法优化的关键之处在于意识到：只有那算法优化的关键之处在于意识到：只有那些在前一遍松弛中改变了距离估计值的点，才可能引起他们些在前一遍松弛中改变了距离估计值的点，才可能引起他们的邻接点的距离估计值的改变。因此，用一个先进先出的队的邻接点的距离估计值的改变。因此，用一个先进先出的队列来存放被成功松弛的顶点。初始时，源点列来存放被成功松弛的顶点。初始时，源点s入队。当队列不入队。当队列不为空时，取出对首顶点，对它的邻接点进行松弛。如果某个为空时，取出对首顶点，对它的邻接点进行松弛。如果某个邻接点松弛成功，且该邻接点不在队列中，则将其入队。经邻接点松弛成功，且该邻接点不在队列中，则将其入队。经过有限次的松弛操作后，队列将为空，算法结束。过有限次的松弛操作后，队列将为空，算法结束。SPFA算法算法的实现，需要用到一个先进先出的队列的实现，需要用到一个先进先出的队列queue和一个指示顶点是和一个指示顶点是否在队列中的否在队列中的标记数组标记数组mark。第22页，本讲稿共60页SPFA算法 设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用，并且用u点当前的最短路径估计值对离开点当前的最短路径估计值对离开u点所指向的结点点所指向的结点v进行松弛操作，如果进行松弛操作，如果v点点的最短路径估计值有所调整，且的最短路径估计值有所调整，且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.ENQUEUE(Q,v)我们用数组我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图记录每个结点的最短路径估计值，而且用邻接表来存储图G。我。我们采取的方法是动态逼近法：们采取的方法是动态逼近法：第23页，本讲稿共60页floyd-warshall算法算法设设di，j，k是是在只允许经过结点在只允许经过结点1k的情况下的情况下i到到j的最短路长度的最短路长度则它有两种情况（想一想，为什么）：则它有两种情况（想一想，为什么）：如果最短路经过点如果最短路经过点k，那么，那么di，j，k应该等于应该等于di，k，k-1+dk，j，k-1；如果最短路不经过点如果最短路不经过点k，那么，那么di，j，k应该等于应该等于di，j，k-1。综合起来综合起来di，j，k=mindi，k，k-1+dk，j，k-1，di，j，k-1边界条件是边界条件是di，j，0=w(i，j)（不存在的边权为（不存在的边权为）第24页，本讲稿共60页floyd-warshall算法基本的动态规划把k放外层循环，可以节省内存对于每个k，计算每两点的目前最短路for 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)用途：预处理！第25页，本讲稿共60页第26页，本讲稿共60页选址问题选址问题现准备现准备在在n 个个居民点居民点v1,v2,vn中设置一银中设置一银行行.问设在哪个点问设在哪个点,可使最大服务距离最小可使最大服务距离最小?若设置两个银行若设置两个银行,问设在哪两个点问设在哪两个点?模型假设模型假设 假设各假设各个个居民点都有条件设置居民点都有条件设置银行银行,并有路相连并有路相连,且路长已知且路长已知.第27页，本讲稿共60页模型建立与求解模型建立与求解用用Floyd算法求出任意两算法求出任意两个个居民点居民点vi,vj 之间的最短距离之间的最短距离,并用并用dij 表表示示.设置一个银行设置一个银行,银行设银行设在在vi 点点的最大服务距离为的最大服务距离为求求k,使使 即若设置一个银行即若设置一个银行,则银行设在则银行设在vk 点点,可使最大服务距离最小可使最大服务距离最小.设置两个银行设置两个银行,假设银行设假设银行设在在vs,vt 点点使最大服务距离最小使最大服务距离最小.记记则则s,t 满足：满足：进一步进一步,若设置多个银行呢？若设置多个银行呢？第28页，本讲稿共60页求求k,使使 即若设置一个银行即若设置一个银行,则银行设在则银行设在vk 点点,可使最可使最大服务距离最小大服务距离最小.设置两个银行设置两个银行,假设银行设假设银行设在在vs,vt 点点使最使最大服务距离最小大服务距离最小.记记则则s,t 满足：满足：进一步进一步,若设置多个银行呢？若设置多个银行呢？第29页，本讲稿共60页最优贸易最优贸易某国有某国有M个城市个城市N条道路，任意两个城市有道路，有一部分道路为单条道路，任意两个城市有道路，有一部分道路为单行线，一部分为双向道路。行线，一部分为双向道路。某人去该国旅游，从城市某人去该国旅游，从城市1出发到城市出发到城市n结束，他想做水晶球的生结束，他想做水晶球的生意一次挣点旅行费用，每个城市有一个水晶球的价格（买入卖出意一次挣点旅行费用，每个城市有一个水晶球的价格（买入卖出都一样），他可以经过每个城市多次。都一样），他可以经过每个城市多次。问他能挣最多的费用为多少？问他能挣最多的费用为多少？如下图，假设城市如下图，假设城市15的价格为的价格为4，3，5，6，1则选择则选择1-4-5-4-5路线，路线，挣得挣得5第30页，本讲稿共60页分析这是一道非常典型的图论题这是一道非常典型的图论题,如果有扎实的图论基础解决起来并如果有扎实的图论基础解决起来并不困难不困难.解决这道题的关键是发现解决这道题的关键是发现,我们可以将原图中的任意一个强连通我们可以将原图中的任意一个强连通分量收缩为一个点分量收缩为一个点,这个新点的买入价格等于该强连通分量中这个新点的买入价格等于该强连通分量中最小的买入价格最小的买入价格,这个新点的卖出价格等于该强连通分量中最这个新点的卖出价格等于该强连通分量中最大的卖出价格大的卖出价格.这是因为这是因为,这个新点的性质和一个强连通分量是这个新点的性质和一个强连通分量是一样的一样的,如果我们要在一个强连通分量中进行购买操作如果我们要在一个强连通分量中进行购买操作,一定会选择一定会选择买入价格最小的那个点买入价格最小的那个点,如果我们要在一个强连通分量中进行卖出如果我们要在一个强连通分量中进行卖出操作操作,也一定会选择卖出价格最大的那个点也一定会选择卖出价格最大的那个点.第31页，本讲稿共60页分析所以算法就非常清晰了所以算法就非常清晰了.首先利用首先利用DFS将所有的强连通分量收缩将所有的强连通分量收缩,这这样我们就可以得到一个有向无环图样我们就可以得到一个有向无环图G.由于由于G中没有环中没有环,我们可我们可以对以对G进行拓扑排序进行拓扑排序,然后利用递推求得到达某个点然后利用递推求得到达某个点i时时,可能的最低可能的最低买入价格买入价格best(i)是多少是多少,以及该点最终能否到达终点以及该点最终能否到达终点.最后对于所有最后对于所有能够到达终点的点能够到达终点的点p,设其卖出价格为设其卖出价格为sell(p),在在sell(p)-best(p)中取中取最大值即得到答案最大值即得到答案.时间复杂度仅为时间复杂度仅为O(V+E).在实现的时候最好使用栈消除在实现的时候最好使用栈消除DFS中的递归调用中的递归调用,因为图中的点可因为图中的点可以达到以达到100000,当递归深度达到这么大的时候有相当大的几率当递归深度达到这么大的时候有相当大的几率发生栈溢出发生栈溢出.参考实现中采用了非递归实现参考实现中采用了非递归实现DFS.第32页，本讲稿共60页奇怪的电梯奇怪的电梯大楼的每一层楼都可以停电梯，而且第大楼的每一层楼都可以停电梯，而且第i层楼层楼(1=i=N)上有一个数上有一个数字字Ki(0=Ki=N)。电梯只有四个按钮：开，关，上，下。上下的层。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：钮就会失灵。例如：33125代表了代表了Ki(K1=3,K2=3,)，从一楼开，从一楼开始。在一楼，按始。在一楼，按“上上”可以到可以到4楼，按楼，按“下下”是不起作用的，因为没是不起作用的，因为没有有-2楼。那么，从楼。那么，从A楼到楼到B楼至少要按几次按钮呢？楼至少要按几次按钮呢？输入：输入：二行，第一行为三个用空格隔开的正整数，表示二行，第一行为三个用空格隔开的正整数，表示N,A,B(1N200,1A,BN)，第二行为，第二行为N个用空格隔开的正整数，表示个用空格隔开的正整数，表示Ki。输出：仅一行，即最少按键次数输出：仅一行，即最少按键次数,若无法到达，则输出若无法到达，则输出-1。第33页，本讲稿共60页构图LIFT.IN51533125LIFT.OUT3对于对于A楼而言，实际上对它最多只能做楼而言，实际上对它最多只能做2个操作，上到个操作，上到A+X层层或下到或下到A-X层，当然前提是存在层，当然前提是存在A+X或或A-X层。显然，如果把每一层层。显然，如果把每一层楼看做一个顶点，如果楼看做一个顶点，如果A楼可以到楼可以到B楼，则从顶点楼，则从顶点A引一条到顶点引一条到顶点B的边，这样一来，问题就变成了图论中的两顶点间最短路径问题了！的边，这样一来，问题就变成了图论中的两顶点间最短路径问题了！当然权设为当然权设为1就行了。就行了。第34页，本讲稿共60页人穿柱子游戏人穿柱子游戏在一个无限长的条形路上，有n(n=200)个柱子，体积不计，有一个人想从左边走到右边，人近似看成一个半径为R的圆（如下图），问能否实现？第35页，本讲稿共60页构图每个圆的大小完全相同，不存在包含，相切（如果内切，每个圆的大小完全相同，不存在包含，相切（如果内切，就是重合了，如果外切，就是中间不连通的）等等复杂就是重合了，如果外切，就是中间不连通的）等等复杂的关系，只有相交和相离的关系，而且如果的关系，只有相交和相离的关系，而且如果2个圆之间个圆之间相交的话，那么这相交的话，那么这2个圆就是相通的，可以在这个圆就是相通的，可以在这2个圆的个圆的圆心之间连一条边，增加一个源点，与上边有交点的圆圆心之间连一条边，增加一个源点，与上边有交点的圆和源点连一条边，增加一个汇点，与下边有交点的圆和和源点连一条边，增加一个汇点，与下边有交点的圆和汇点连一条边，这样就把一道几何题完全转换成了一道汇点连一条边，这样就把一道几何题完全转换成了一道图论题，只要判断源点和汇点之间是否有路就可以了图论题，只要判断源点和汇点之间是否有路就可以了第36页，本讲稿共60页奇怪的数列奇怪的数列编程输入编程输入3个整数个整数n，p，q，寻找一个由整数组成的数列，寻找一个由整数组成的数列（a1，a2，an），要求：其中任意连续），要求：其中任意连续p项之和为正数，项之和为正数，任意连续任意连续q项之和为负数。项之和为负数。0n100，0p，qn，若不存，若不存在这样的整数数列，则输出在这样的整数数列，则输出NO；否则输出满足条件的；否则输出满足条件的一个数列即可。一个数列即可。输入格式：输入格式：仅一行分别表示仅一行分别表示n，p，q，之间用一个空格隔开。，之间用一个空格隔开。输出格式：输出格式：只有一行，有解即输出这个数列，每个数之间用一个空格隔只有一行，有解即输出这个数列，每个数之间用一个空格隔开。否则输出开。否则输出NO。第37页，本讲稿共60页分析如果我们按常规思想，直接将第如果我们按常规思想，直接将第i个整数个整数ai开始的开始的k个整数之和描述成个整数之和描述成多项式多项式ai+ai+1+ai+k-1的话，问题就很难再往下思考和解决了。的话，问题就很难再往下思考和解决了。所以，我们不防换个角度，暂且撇去每一项数究竟为何值的具所以，我们不防换个角度，暂且撇去每一项数究竟为何值的具体细节，而将注意力集中至连续性这一特点上。设体细节，而将注意力集中至连续性这一特点上。设si表示数列前表示数列前i个整数之和，即个整数之和，即si=a1+a2+ai。其中。其中s0=0(0in)。显然根据题意，。显然根据题意，有：有：sisi+p(0in-p)si+qsj(0i，jn)，则从，则从si往往sj引出一条有向边。引出一条有向边。第38页，本讲稿共60页构图对于n=6，p=5，q=3的情况，我们可以建立下图：第39页，本讲稿共60页对图进行拓扑排序；对图进行拓扑排序；if图有回路图有回路then无解退出无解退出else生成拓扑序列生成拓扑序列order0ordern；那么如果得到了一个拓扑序列，该如何转换成那么如果得到了一个拓扑序列，该如何转换成s数组呢？因为拓扑序列中顶点对应的数组呢？因为拓扑序列中顶点对应的s值是递减的，其中值是递减的，其中s0=0。如果如果orderi=0，则依次设定，则依次设定sorder0=i，sorder1=i-1，sorderi-1=1，sorderi=0，sorderi+1=-1，sordern=i-n。例如，对于上图所示的有向图，可以得到下表：例如，对于上图所示的有向图，可以得到下表：所以，得到所以，得到s0=0，s1=-3，s2=2，s3=-1，s4=-4，s5=1，s6=-2。再根据。再根据s的定义，由：的定义，由：ai=(a0+a1+ai-1+ai)-(a0+a1+ai-1)=si-si-1，求出：，求出：a1=s1-s0=-3，a2=s2-s1=5，a3=s3-s2=-3，a4=s4-s3=-3，a5=s5-s4=5，a6=s6-s5=-3。显然这个整数数列的任意连续。显然这个整数数列的任意连续个整数之和为正，任意连续个整数之和为负。个整数之和为正，任意连续个整数之和为负。第40页，本讲稿共60页牧场规划牧场规划小可可的好朋友小可可的好朋友Sealock最喜欢吃花生了，于是借用了小可可最喜欢吃花生了，于是借用了小可可的牧场从事花生选种试验。他以网格的方式，非常规整地把的牧场从事花生选种试验。他以网格的方式，非常规整地把牧场分割成牧场分割成M*N个矩形区域个矩形区域(M*N5000)，由于各个区域中地水，由于各个区域中地水面、沼泽面积各不相同，因此各区域地实际可种植面积也各不相面、沼泽面积各不相同，因此各区域地实际可种植面积也各不相同，已知区域同，已知区域(i,j)地可种面积使地可种面积使A(i,j)。每个区域种最多只能种植一个品种地花生。可种植面积为每个区域种最多只能种植一个品种地花生。可种植面积为零地区域不能被选择用来从事选种试验，同时为了防止花零地区域不能被选择用来从事选种试验，同时为了防止花粉传播到相邻区域造成试验结果不正确，任何两个相邻的粉传播到相邻区域造成试验结果不正确，任何两个相邻的区域都不可以同时种植花生。这里说的相邻指的是两个区区域都不可以同时种植花生。这里说的相邻指的是两个区域有公共边，仅仅有公共点的两个区域不算做相邻。域有公共边，仅仅有公共点的两个区域不算做相邻。小可可准备帮助小可可准备帮助Sealock规划一下如何选择种植区域，才能使规划一下如何选择种植区域，才能使得实际可种植面积总和最大。得实际可种植面积总和最大。第41页，本讲稿共60页构图将试验田转化为点、并连接相邻的试验田后可以发现，我们得到的是一个二分图。将试验田转化为点、并连接相邻的试验田后可以发现，我们得到的是一个二分图。通过对原图的黑白染色，可以把其中的一部分称为白点、另一部分称为黑点。由通过对原图的黑白染色，可以把其中的一部分称为白点、另一部分称为黑点。由二分图建立网络：加入源点和汇点，从源点向每个白点引一条边，容量为白点对二分图建立网络：加入源点和汇点，从源点向每个白点引一条边，容量为白点对应试验田的面积；从每个黑点向汇点引边，容量为该黑点的对应面积。最后将相应试验田的面积；从每个黑点向汇点引边，容量为该黑点的对应面积。最后将相邻点之间的边改为网络中的边，由白点指向黑点，容量为正无穷。通过求网络最邻点之间的边改为网络中的边，由白点指向黑点，容量为正无穷。通过求网络最大流得到它的最小割，即为最优方案。大流得到它的最小割，即为最优方案。S T图图1 建立网建立网络络第42页，本讲稿共60页瘦陀陀和胖陀陀瘦陀陀和胖陀陀一场可怕的战争后，瘦陀陀和他的好朋友胖陀陀将要一场可怕的战争后，瘦陀陀和他的好朋友胖陀陀将要凯旋。凯旋。瘦陀陀处在城市瘦陀陀处在城市A胖陀陀处在另外一个未知的城市胖陀陀处在另外一个未知的城市他们打算选一个城市他们打算选一个城市X（这个由瘦陀陀来决定）（这个由瘦陀陀来决定）胖陀陀会赶在瘦陀陀之前到达城市胖陀陀会赶在瘦陀陀之前到达城市X然后等待瘦陀陀也赶到城市然后等待瘦陀陀也赶到城市X与他汇合，并举办一次庆祝宴会与他汇合，并举办一次庆祝宴会（由瘦陀陀请客）（由瘦陀陀请客）接着一起回到他们的家乡城市接着一起回到他们的家乡城市B由于胖陀陀嘴馋，他要求举办宴会的城市必须是瘦陀陀回家的路由于胖陀陀嘴馋，他要求举办宴会的城市必须是瘦陀陀回家的路线中举办宴会最贵的一个城市。线中举办宴会最贵的一个城市。第43页，本讲稿共60页一个例子（续）瘦陀陀正专注地看回家的地图瘦陀陀正专注地看回家的地图地图上标有地图上标有n（n200）个城市）个城市和某些城市间直达的道路和某些城市间直达的道路以及每条道路的过路费以及每条道路的过路费瘦陀陀还知道在每一座城市举瘦陀陀还知道在每一座城市举办宴会的花费。办宴会的花费。给出地图和给出地图和A、B的位置的位置请你告诉瘦陀陀回家的最小费请你告诉瘦陀陀回家的最小费用用你的程序会接收到多次询问你的程序会接收到多次询问即对于每对城市即对于每对城市(c1,c2)，你的，你的程序应该立刻给出瘦陀陀从程序应该立刻给出瘦陀陀从c1到到c2的最小花费。的最小花费。第44页，本讲稿共60页分析胖陀陀规定必须在最贵的城市举办宴会胖陀陀规定必须在最贵的城市举办宴会因此不能简单地选择一条最短路走因此不能简单地选择一条最短路走若路上有一个花费特别贵的城市若路上有一个花费特别贵的城市对于每个点对于每个点X，如果在那里办宴会，如果在那里办宴会如何求最短路？如何求最短路？多个询问怎么处理？多个询问怎么处理？floyd计算每两点的距离？计算每两点的距离？SSSP就可以胜任吗？就可以胜任吗？AB=AX+XB第45页，本讲稿共60页树网的核树网的核给出一棵无根树，边上有权。称树的最长路径为直径，定义路径的偏心距为：点到路径的上的点的最小值的最大值，给出一个s，找出直径上的某段长度不超过s的路径，使得偏心距最小。第46页，本讲稿共60页分析考虑到树的性质，对于任意两点，最短路考虑到树的性质，对于任意两点，最短路=联通路联通路=最长路。最长路。首先用首先用floyd算法求出任意两点之间最短路。同时可以求出最算法求出任意两点之间最短路。同时可以求出最长路径上都有哪些点。由于这是一棵树，最短路必然唯一。长路径上都有哪些点。由于这是一棵树，最短路必然唯一。设设mida,b是是a,b之间的联通路上的一个中间点。考虑问题的解，之间的联通路上的一个中间点。考虑问题的解，构造一个函数构造一个函数F(k,a,b)为为K到到ab间的最短路的长度。则间的最短路的长度。则f(k,a,b)=mindk,mida,b,fk,a,mida,b,fk,mida,b,b写出了这个方程，便不难得出一个三次方的算法。在实际做写出了这个方程，便不难得出一个三次方的算法。在实际做的时候，可以把的时候，可以把k放在最外层枚举，这样内层实际上只用到放在最外层枚举，这样内层实际上只用到了了f的后面的后面2维，用维，用2维数组记录即可。维数组记录即可。第47页，本讲稿共60页双栈排序双栈排序有两个队列和两个栈有两个队列和两个栈,分别命名为队列分别命名为队列1(q),队列队列2(q2),栈栈1(s1)和栈和栈2(s2).最初的时候最初的时候,q2,s1和和s2都为空都为空,而而q中有中有n个数个数(n=1000),为为1n的某个排列的某个排列.现在支持如下四种操作现在支持如下四种操作:a操作操作,将将q的首元素提取出并加入的首元素提取出并加入s1的栈顶的栈顶.b操作操作,将将s1的栈顶元素弹出并加入的栈顶元素弹出并加入q2的队列尾的队列尾.c操作操作,将将q的首元素提取出并加入的首元素提取出并加入s2的栈顶的栈顶.d操作操作,将将s2的栈顶元素弹出并加入的栈顶元素弹出并加入q2的队列尾的队列尾.请判断请判断,是否可以经过一系列操作之后是否可以经过一系列操作之后,使得使得q2中依次存储中依次存储着着1,2,3,n.如果可以如果可以,求出字典序最小的一个操作序列求出字典序最小的一个操作序列.第48页，本讲稿共60页考虑单栈例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;第49页，本讲稿共60页定理定理：对于任意两个数定理：对于任意两个数qi和和qj来说来说,它们不能压入同一个栈中的它们不能压入同一个栈中的充要条件充要条件p是是:存在一个存在一个k,使得使得ijk且且qkqiqi,这显然是不正确的这显然是不正确的.第50页，本讲稿共60页证明必要性：也就是必要性：也就是,如果两个数不可以压入同一个栈如果两个数不可以压入同一个栈,那么它们一定那么它们一定满足条件满足条件p.这里我们来证明它的逆否命题这里我们来证明它的逆否命题,也就是也就是如果不满足条件如果不满足条件p,那么这两个数一定可以压入同一个栈那么这两个数一定可以压入同一个栈.“不满足条件不满足条件p有两种情况有两种情况:一种是对于任意一种是对于任意ijk且且qiqi;另另一种是对于任意一种是对于任意iqj.第一种情况下第一种情况下,很显然很显然,在在qk被压入栈的时候被压入栈的时候,qi已经被弹出栈已经被弹出栈.那么那么,qk不会对不会对qj产生任何影响产生任何影响(这里可能有点乱这里可能有点乱,因为看起来因为看起来,当当qjqK的时候的时候,是会有影响的是会有影响的,但实际上但实际上,这还需要另一个数这还需要另一个数R,满足满足JKR且且qrqjqk,也就是证明充分性的时候所说的情况也就是证明充分性的时候所说的情况而事而事实上我们现在并不考虑这个实上我们现在并不考虑这个r,所以说所以说qk对对qj没有影响没有影响).第二种情况下第二种情况下,我们可以发现这其实就是一个降序序列我们可以发现这其实就是一个降序序列,所以所有数所以所有数字都可以压入同一个栈字都可以压入同一个栈.这样这样,原命题的逆否命题得证原命题的逆否命题得证,所以原命题得证所以原命题得证.此时此时,条件条件p为为qi和和qj不能压入同一个栈的充要条件也得证不能压入同一个栈的充要条件也得证.第51页，本讲稿共60页构图构图这样这样,我们对所有的数对我们对所有的数对(i,j)满足满足1=ij=n,检查是否存检查是否存在在ijk满足满足qkqiqj.如果存在如果存在,那么在点那么在点i和点和点j之之间连一条无向边间连一条无向边,表示表示qi和和qj不能压入同一个栈不能压入同一个栈.二分图的两部分看作两个栈二分图的两部分看作两个栈,因为二分图的同一部分因为二分图的同一部分内不会出现任何连边内不会出现任何连边,也就相当于不能压入同一个栈的也就相当于不能压入同一个栈的所有结点都分到了两个栈中所有结点都分到了两个栈中.此时我们只考虑检查是否有解此时我们只考虑检查是否有解,所以只要所以只要O(n)检查出检查出这个图是不是二分图这个图是不是二分图,就可以得知是否有解就可以得知是否有解.第52页，本讲稿共60页深度优先搜索求解检查有解的问题已经解决检查有解的问题已经解决.接下来的问题是接下来的问题是,如何找到字典序如何找到字典序最小的解最小的解.实际上实际上,可以发现可以发现,如果把二分图染成如果把二分图染成1和和2两种颜色两种颜色,那么结那么结点染色为点染色为1对应当前结点被压入对应当前结点被压入s1,为为2对应被压入对应被压入s2.为了字为了字典序尽量小典序尽量小,我们希望让编号小的结点优先压入我们希望让编号小的结点优先压入s1.又发现二分图的不同连通分量之间的染色是互不影响的又发现二分图的不同连通分量之间的染色是互不影响的,所以可所以可以每次选取一个未染色的编号最小的结点以每次选取一个未染色的编号最小的结点,将它染色为将它染色为1并从并从它开始它开始DFS染色染色,直到所有结点都被染色为止直到所有结点都被染色为止.这样这样,我们就得我们就得到了每个结点应该压入哪个栈中到了每个结点应该压入哪个栈中。还有一点小问题还有一点小问题,就是如果对于数对就是如果对于数对(i,j),都去枚举检查是否存都去枚举检查是否存在在k，使得，使得qkqIM第53页，本讲稿共60页最优乘车（最优乘车（NOI97）一名旅客最近到一名旅客最近到H城旅游，他很想去城旅游，他很想去S公园游玩，但如果从公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达他所在的饭店没有一路巴士可以直接到达S公园，则他可能要公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士,这样换乘几次后到达这样换乘几次后到达S公园。公园。现在用整数现在用整数1，2，N给给H城的所有的巴士站编号，约定城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为这名旅客所在饭店的巴士站编号为1，2，S，公园巴士，公园巴士站的编号为站的编号为N。写一个程序，帮助这名旅客寻找一个最优乘车方案写一个程序，帮助这名旅客寻找一个最优乘车方案,使他在使他在从饭店乘车到从饭店乘车到S公园的过程中换车的次数最少。公园的过程中换车的次数最少。输入输入N和和M条公交线路信息条公交线路信息求最少换车的次数求最少换车的次数第54页，本讲稿共60页模型的构建我们来分析样例我们来分析样例3767473621356747362135第55页，本讲稿共60页考察考察4736这条线路。由于巴士在同一线路上行这条线路。由于巴士在同一线路上行走不需换车，我们可设走不需换车，我们可设47，43，46，73，76，36这些边的权值都为这些边的