图论模型的构建精.ppt

《图论模型的构建精.ppt》由会员分享，可在线阅读，更多相关《图论模型的构建精.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论模型的构建第1页，本讲稿共47页NOIP若干图论的考题Core(2007)Core(2007):图的多源最短路算法及其简单处理图的多源最短路算法及其简单处理双栈排序双栈排序(2008):栈的应用栈的应用+二分图的搜索二分图的搜索最优贸易最优贸易(2009):基本图论基本图论第2页，本讲稿共47页问题：求网线线序问题：求网线线序网线从机房连接到办公室在机房，所有网线从左到右编号为1,2,3,N 给出每两条线是否交叉的信息，请计算办公室内从左到右各条线的编号 第3页，本讲稿共47页选址问题选址问题现准备现准备在在n 个个居民点居民点v1,v2,vn中设置一银行中设置一银行.问设在哪个点问设在哪

2、个点,可使最大服务距离最小可使最大服务距离最小?若设置两若设置两个银行个银行,问设在哪两个点问设在哪两个点?模型假设模型假设 假设各假设各个个居民点都有条件设置银居民点都有条件设置银行行,并有路相连并有路相连,且路长已知且路长已知.第4页，本讲稿共47页模型建立与求解模型建立与求解用用Floyd算法求出任意两算法求出任意两个个居民点居民点vi,vj 之间的最短距离之间的最短距离,并用并用dij 表示表示.设置一个银行设置一个银行,银行设银行设在在vi 点点的最大服务距离为的最大服务距离为求求k,使使 即若设置一个银行即若设置一个银行,则银行设在则银行设在vk 点点,可使最大服务距离最小可使最大

3、服务距离最小.设置两个银行设置两个银行,假设银行设假设银行设在在vs,vt 点点使最大服务距离最小使最大服务距离最小.记记则则s,t 满足：满足：进一步进一步,若设置多个银行呢？若设置多个银行呢？第5页，本讲稿共47页求求k,使使 即若设置一个银行即若设置一个银行,则银行设在则银行设在vk 点点,可使最大服可使最大服务距离最小务距离最小.设置两个银行设置两个银行,假设银行设假设银行设在在vs,vt 点点使最大使最大服务距离最小服务距离最小.记记则则s,t 满足：满足：进一步进一步,若设置多个银行呢？若设置多个银行呢？第6页，本讲稿共47页最优贸易最优贸易某国有某国有M个城市个城市N条道路，任意

4、两个城市有道路，有一部分道条道路，任意两个城市有道路，有一部分道路为单行线，一部分为双向道路。路为单行线，一部分为双向道路。某人去该国旅游，从城市某人去该国旅游，从城市1出发到城市出发到城市n结束，他想做水晶球的生意一结束，他想做水晶球的生意一次挣点旅行费用，每个城市有一个水晶球的价格（买入卖出都一样），次挣点旅行费用，每个城市有一个水晶球的价格（买入卖出都一样），他可以经过每个城市多次。他可以经过每个城市多次。问他能挣最多的费用为多少？问他能挣最多的费用为多少？如下图，假设城市如下图，假设城市15的价格为的价格为4，3，5，6，1则选择则选择1-4-5-4-5路线，路线，挣得挣得5第7页，本

5、讲稿共47页分析这是一道非常典型的图论题这是一道非常典型的图论题,如果有扎实的图论基础解决起来并不如果有扎实的图论基础解决起来并不困难困难.解决这道题的关键是发现解决这道题的关键是发现,我们可以将原图中的任意一个强连通分我们可以将原图中的任意一个强连通分量收缩为一个点量收缩为一个点,这个新点的买入价格等于该强连通分量中最小的这个新点的买入价格等于该强连通分量中最小的买入价格买入价格,这个新点的卖出价格等于该强连通分量中最大的卖出价这个新点的卖出价格等于该强连通分量中最大的卖出价格格.这是因为这是因为,这个新点的性质和一个强连通分量是一样的这个新点的性质和一个强连通分量是一样的,如果我如果我们要

6、在一个强连通分量中进行购买操作们要在一个强连通分量中进行购买操作,一定会选择买入价格最小一定会选择买入价格最小的那个点的那个点,如果我们要在一个强连通分量中进行卖出操作如果我们要在一个强连通分量中进行卖出操作,也一定也一定会选择卖出价格最大的那个点会选择卖出价格最大的那个点.第8页，本讲稿共47页分析所以算法就非常清晰了所以算法就非常清晰了.首先利用首先利用DFS将所有的强连通分量收将所有的强连通分量收缩缩,这样我们就可以得到一个有向无环图这样我们就可以得到一个有向无环图G.由于由于G中没有环中没有环,我们可以对我们可以对G进行拓扑排序进行拓扑排序,然后利用递推求得到达某个点然后利用递推求得到

7、达某个点i时时,可能的最低买入价格可能的最低买入价格best(i)是多少是多少,以及该点最终能否到以及该点最终能否到达终点达终点.最后对于所有能够到达终点的点最后对于所有能够到达终点的点p,设其卖出价格为设其卖出价格为sell(p),在在sell(p)-best(p)中取最大值即得到答案中取最大值即得到答案.时间复杂度仅时间复杂度仅为为O(V+E).在实现的时候最好使用栈消除在实现的时候最好使用栈消除DFS中的递归调用中的递归调用,因为图中的点可因为图中的点可以达到以达到100000,当递归深度达到这么大的时候有相当大的几率发生当递归深度达到这么大的时候有相当大的几率发生栈溢出栈溢出.参考实现

8、中采用了非递归实现参考实现中采用了非递归实现DFS.第9页，本讲稿共47页奇怪的电梯奇怪的电梯大楼的每一层楼都可以停电梯，而且第大楼的每一层楼都可以停电梯，而且第i层楼层楼(1=i=N)上有上有一个数字一个数字Ki(0=Ki=N)。电梯只有四个按钮：开，关，上，。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：能满足要求，相应的按钮就会失灵。例如：33125代表了代表了Ki(K1=3,K2=3,)，从一楼开始。在一楼，按，从一楼开始。在一楼，按“上上”可以到可以到4楼，楼

9、，按按“下下”是不起作用的，因为没有是不起作用的，因为没有-2楼。那么，从楼。那么，从A楼到楼到B楼至楼至少要按几次按钮呢？少要按几次按钮呢？输入：输入：二行，第一行为三个用空格隔开的正整数，表示二行，第一行为三个用空格隔开的正整数，表示N,A,B(1N200,1A,BN)，第二行为，第二行为N个用空格隔开的正整数，个用空格隔开的正整数，表示表示Ki。输出：仅一行，即最少按键次数输出：仅一行，即最少按键次数,若无法到达，则输出若无法到达，则输出-1。第10页，本讲稿共47页构图LIFT.IN51533125LIFT.OUT3对于对于A楼而言，实际上对它最多只能做楼而言，实际上对它最多只能做2个

10、操作，上到个操作，上到A+X层或下到层或下到A-X层，当然前提是存在层，当然前提是存在A+X或或A-X层。显然，如果把每一层楼看做一个层。显然，如果把每一层楼看做一个顶点，如果顶点，如果A楼可以到楼可以到B楼，则从顶点楼，则从顶点A引一条到顶点引一条到顶点B的边，这样一的边，这样一来，问题就变成了图论中的两顶点间最短路径问题了！当然权设为来，问题就变成了图论中的两顶点间最短路径问题了！当然权设为1就行了。就行了。第11页，本讲稿共47页人穿柱子游戏人穿柱子游戏在一个无限长的条形路上，有n(n=200)个柱子，体积不计，有一个人想从左边走到右边，人近似看成一个半径为R的圆（如下图），问能否实现？

11、第12页，本讲稿共47页构图每个圆的大小完全相同，不存在包含，相切（如果内每个圆的大小完全相同，不存在包含，相切（如果内切，就是重合了，如果外切，就是中间不连通的）等切，就是重合了，如果外切，就是中间不连通的）等等复杂的关系，只有相交和相离的关系，而且如果等复杂的关系，只有相交和相离的关系，而且如果2个圆之间相交的话，那么这个圆之间相交的话，那么这2个圆就是相通的，可以个圆就是相通的，可以在这在这2个圆的圆心之间连一条边，增加一个源点，与个圆的圆心之间连一条边，增加一个源点，与上边有交点的圆和源点连一条边，增加一个汇点，与上边有交点的圆和源点连一条边，增加一个汇点，与下边有交点的圆和汇点连一条

12、边，这样就把一道几何下边有交点的圆和汇点连一条边，这样就把一道几何题完全转换成了一道图论题，只要判断源点和汇点之题完全转换成了一道图论题，只要判断源点和汇点之间是否有路就可以了间是否有路就可以了第13页，本讲稿共47页奇怪的数列奇怪的数列编程输入编程输入3个整数个整数n，p，q，寻找一个由整数组成的数，寻找一个由整数组成的数列（列（a1，a2，an），要求：其中任意连续），要求：其中任意连续p项之和项之和为正数，任意连续为正数，任意连续q项之和为负数。项之和为负数。0n100，0p，qn，若不存在这样的整数数列，则输出，若不存在这样的整数数列，则输出NO；否则输出满；否则输出满足条件的一个数列

13、即可。足条件的一个数列即可。输入格式：输入格式：仅一行分别表示仅一行分别表示n，p，q，之间用一个空格隔开。，之间用一个空格隔开。输出格式：输出格式：只有一行，有解即输出这个数列，每个数之间用一个只有一行，有解即输出这个数列，每个数之间用一个空格隔开。否则输出空格隔开。否则输出NO。第14页，本讲稿共47页分析如果我们按常规思想，直接将第如果我们按常规思想，直接将第i个整数个整数ai开始的开始的k个整数之和描个整数之和描述成多项式述成多项式ai+ai+1+ai+k-1的话，问题就很难再往下思考和解决了。的话，问题就很难再往下思考和解决了。所以，我们不防换个角度，暂且撇去每一项数究竟为何值的具体

14、所以，我们不防换个角度，暂且撇去每一项数究竟为何值的具体细节，而将注意力集中至连续性这一特点上。设细节，而将注意力集中至连续性这一特点上。设si表示数列前表示数列前i个个整数之和，即整数之和，即si=a1+a2+ai。其中。其中s0=0(0in)。显然根据题。显然根据题意，有：意，有：sisi+p(0in-p)si+qsj(0i，jn)，则从，则从si往往sj引出一条有向边。引出一条有向边。第15页，本讲稿共47页构图对于n=6，p=5，q=3的情况，我们可以建立下图：第16页，本讲稿共47页对图进行拓扑排序；对图进行拓扑排序；if图有回路图有回路then无解退出无解退出else生成拓扑序列生

15、成拓扑序列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。再根据

16、。再根据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。显然这个整数数列的任意连续个。显然这个整数数列的任意连续个整数之和为正，任意连续个整数之和为负。整数之和为正，任意连续个整数之和为负。第17页，本讲稿共47页牧场规划牧场规划小可可的好朋友小可可的好朋友Sealock最喜欢吃花生了，于是借用了小可可最喜欢吃花生了，于是借用了小可可的牧场从事花生选种试验。他以网格的方式，非常规整地把

17、的牧场从事花生选种试验。他以网格的方式，非常规整地把牧场分割成牧场分割成M*N个矩形区域个矩形区域(M*N5000)，由于各个区域中地，由于各个区域中地水面、沼泽面积各不相同，因此各区域地实际可种植面积也水面、沼泽面积各不相同，因此各区域地实际可种植面积也各不相同，已知区域各不相同，已知区域(i,j)地可种面积使地可种面积使A(i,j)。每个区域种最多只能种植一个品种地花生。可种植面积为零地每个区域种最多只能种植一个品种地花生。可种植面积为零地区域不能被选择用来从事选种试验，同时为了防止花粉传播到区域不能被选择用来从事选种试验，同时为了防止花粉传播到相邻区域造成试验结果不正确，任何两个相邻的区

18、域都不可以相邻区域造成试验结果不正确，任何两个相邻的区域都不可以同时种植花生。这里说的相邻指的是两个区域有公共边，仅仅同时种植花生。这里说的相邻指的是两个区域有公共边，仅仅有公共点的两个区域不算做相邻。有公共点的两个区域不算做相邻。小可可准备帮助小可可准备帮助Sealock规划一下如何选择种植区域，才能规划一下如何选择种植区域，才能使得实际可种植面积总和最大。使得实际可种植面积总和最大。第18页，本讲稿共47页构图将试验田转化为点、并连接相邻的试验田后可以发现，我们得到的是一个二分图。将试验田转化为点、并连接相邻的试验田后可以发现，我们得到的是一个二分图。通过对原图的黑白染色，可以把其中的一部

19、分称为白点、另一部分称为黑点。由通过对原图的黑白染色，可以把其中的一部分称为白点、另一部分称为黑点。由二分图建立网络：加入源点和汇点，从源点向每个白点引一条边，容量为白点对二分图建立网络：加入源点和汇点，从源点向每个白点引一条边，容量为白点对应试验田的面积；从每个黑点向汇点引边，容量为该黑点的对应面积。最后将相应试验田的面积；从每个黑点向汇点引边，容量为该黑点的对应面积。最后将相邻点之间的边改为网络中的边，由白点指向黑点，容量为正无穷。通过求网络最邻点之间的边改为网络中的边，由白点指向黑点，容量为正无穷。通过求网络最大流得到它的最小割，即为最优方案。大流得到它的最小割，即为最优方案。S T图图

20、1 建立网建立网络络第19页，本讲稿共47页和平委员会（和平委员会（SPO）要选一个委员会，但是出现了一个问题，某些代表是有矛盾的，要选一个委员会，但是出现了一个问题，某些代表是有矛盾的，不能同时选到委员会里来。现在有不能同时选到委员会里来。现在有n个政党，每个政党只有两个代个政党，每个政党只有两个代表，要从每个政党中选择一个代表，使委员会里的人都是友好的。表，要从每个政党中选择一个代表，使委员会里的人都是友好的。所有的人用所有的人用1到到2n来编号，来编号，2i-1和和2i属于同一个政党。属于同一个政党。读入政党总数，以及不友好的人的对数。读入政党总数，以及不友好的人的对数。计算是否可以建立

21、委员会。如果可以，给出方案。计算是否可以建立委员会。如果可以，给出方案。输入：第一行有两个整数输入：第一行有两个整数n和和m，1=n=8000，0=m=20000。分。分别表示政党的总数以及不友好的关系数。接下来的别表示政党的总数以及不友好的关系数。接下来的m行，每行整数行，每行整数a和和b,1=ab=2n，表示这两个人是有矛盾的。，表示这两个人是有矛盾的。输出：无解则输出输出：无解则输出NIE。否则打印。否则打印n行，从小到大输出你的方案行，从小到大输出你的方案中各人的编号。任意可行解都是可以的。中各人的编号。任意可行解都是可以的。第20页，本讲稿共47页分析：原题可描述为：有n个组，第i个

22、组里有两个节点Ai,Ai。需要从每个组中选出一个。而某些点不可以同时选出（称之为不相容）。任务是保证选出的n个点都能两两相容。（在这里把Ai,Ai 的定义稍稍放宽一些，它们同时表示属于同一个组的两个节点。也就是说，如果我们描述Ai，那么描述这个组的另一个节点就可以用Ai）第21页，本讲稿共47页初步构图如果Ai与Aj不相容，那么如果选择了Ai，必须选择Aj；同样，如果选择了Aj，就必须选择Ai。Ai Aj Aj Ai 这样的两条边对称对称我们从一个例子来看：第22页，本讲稿共47页假设4个组，不和的代表为：1和4，2和3，7和3，那么构图：13245678假设：首先选13必须选，2不可选8必须

23、选，4、7不可选5、6可以任选一个第23页，本讲稿共47页 矛盾矛盾矛盾矛盾的情况为：存在Ai，使得Ai既必须被选又不可选。得到算法算法算法算法1 1 1 1：枚举每一对尚未确定的Ai,Ai，任选1个，推导出相关的组，若不矛盾，则可选择；否则选另1个，同样推导。若矛盾，问题必定无解。13245678第24页，本讲稿共47页此算法正确性简要说明：由于Ai,Ai 都是尚未确定的，它们不与之前的组相关联，前面的选择不会影响Ai,Ai。算法的时间复杂度在最坏的情况下为O(nm)。在这个算法中，并没有很好的利用图中边的对称对称性第25页，本讲稿共47页先看这样一个结构：更一般的说：在每个一个环里，任意一

24、个点的选择代表将要选择此环里的每一个点。不妨把环收缩成一个子节点（规定这样的环是极大强连通子图极大强连通子图）。新节点的选择表示选择这个节点所对应的环中的每一个节点。此图中1和3构成一个环环，这样1和3要么都被选择，要么都不被选。2和4同样如此。图的收缩13245678第26页，本讲稿共47页对于原图中的每条边Ai Aj（设Ai属于环Si，Aj属于环Sj）如果SiSj，则在新图中连边：Si Sjn 这样构造出一个新的有向无环图。有向无环图。n 此图与原图等价等价。13245678S1 S1S2 S2 S3 S3图的收缩第27页，本讲稿共47页算法2通过求强连通分量，可以把图转换成新的有向无环图

25、，在通过求强连通分量，可以把图转换成新的有向无环图，在这个基础上，介绍一个新的算法。这个基础上，介绍一个新的算法。新算法中，如果存在一对新算法中，如果存在一对A Ai i,A,Ai i 属于同一个环，则判无解，属于同一个环，则判无解，否则将采用拓扑排序，以自底向上的顺序进行推导，一定否则将采用拓扑排序，以自底向上的顺序进行推导，一定能找到可行解。能找到可行解。第28页，本讲稿共47页算法算法算法算法2 2 2 2的流程：的流程：1 1构图构图2 2求图的极大强连通子图求图的极大强连通子图3 3把把每每个个子子图图收收缩缩成成单单个个节节点点，根根据据原原图图关关系系构构造造一一个个有有向无环图

26、向无环图4 4判断是否有解，无解则输出（退出）判断是否有解，无解则输出（退出）5 5对新图进行拓扑排序对新图进行拓扑排序6 6自底向上进行选择、删除自底向上进行选择、删除7 7输出输出第29页，本讲稿共47页瘦陀陀和胖陀陀瘦陀陀和胖陀陀一场可怕的战争后，瘦陀陀和他的好朋友胖陀陀将一场可怕的战争后，瘦陀陀和他的好朋友胖陀陀将要凯旋。要凯旋。瘦陀陀处在城市瘦陀陀处在城市A胖陀陀处在另外一个未知的城市胖陀陀处在另外一个未知的城市他们打算选一个城市他们打算选一个城市X（这个由瘦陀陀来决定）（这个由瘦陀陀来决定）胖陀陀会赶在瘦陀陀之前到达城市胖陀陀会赶在瘦陀陀之前到达城市X然后等待瘦陀陀也赶到城市然后等

27、待瘦陀陀也赶到城市X与他汇合，并举办一次庆祝宴与他汇合，并举办一次庆祝宴会（由瘦陀陀请客）会（由瘦陀陀请客）接着一起回到他们的家乡城市接着一起回到他们的家乡城市B由于胖陀陀嘴馋，他要求举办宴会的城市必须是瘦陀陀由于胖陀陀嘴馋，他要求举办宴会的城市必须是瘦陀陀回家的路线中举办宴会最贵的一个城市。回家的路线中举办宴会最贵的一个城市。第30页，本讲稿共47页一个例子（续）瘦陀陀正专注地看回家的地图瘦陀陀正专注地看回家的地图地图上标有地图上标有n（n200）个城市）个城市和某些城市间直达的道路和某些城市间直达的道路以及每条道路的过路费以及每条道路的过路费瘦陀陀还知道在每一座城市举瘦陀陀还知道在每一座城

28、市举办宴会的花费。办宴会的花费。给出地图和给出地图和A、B的位置的位置请你告诉瘦陀陀回家的最小费请你告诉瘦陀陀回家的最小费用用你的程序会接收到多次询问你的程序会接收到多次询问即对于每对城市即对于每对城市(c1,c2)，你的，你的程序应该立刻给出瘦陀陀从程序应该立刻给出瘦陀陀从c1到到c2的最小花费。的最小花费。第31页，本讲稿共47页分析胖陀陀规定必须在最贵的城市举办宴会胖陀陀规定必须在最贵的城市举办宴会因此不能简单地选择一条最短路走因此不能简单地选择一条最短路走若路上有一个花费特别贵的城市若路上有一个花费特别贵的城市对于每个点对于每个点X，如果在那里办宴会，如果在那里办宴会如何求最短路？如何

29、求最短路？多个询问怎么处理？多个询问怎么处理？floyd计算每两点的距离？计算每两点的距离？SSSP就可以胜任吗？就可以胜任吗？AB=AX+XB第32页，本讲稿共47页树网的核树网的核给出一棵无根树，边上有权。称树的最长路径为直径，定义路径的偏心距为：点到路径的上的点的最小值的最大值，给出一个s，找出直径上的某段长度不超过s的路径，使得偏心距最小。第33页，本讲稿共47页分析考虑到树的性质，对于任意两点，最短路考虑到树的性质，对于任意两点，最短路=联通路联通路=最长路。最长路。首先用首先用floyd算法求出任意两点之间最短路。同时可以求出最长路径算法求出任意两点之间最短路。同时可以求出最长路径

30、上都有哪些点。由于这是一棵树，最短路必然唯一。设上都有哪些点。由于这是一棵树，最短路必然唯一。设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的

31、后的后面面2维，用维，用2维数组记录即可。维数组记录即可。第34页，本讲稿共47页双栈排序双栈排序有两个队列和两个栈有两个队列和两个栈,分别命名为队列分别命名为队列1(q),队列队列2(q2),栈栈1(s1)和栈和栈2(s2).最初的时候最初的时候,q2,s1和和s2都为空都为空,而而q中有中有n个数个数(n=1000),为为1n的某个排列的某个排列.现在支持如下四种操作现在支持如下四种操作:a操作操作,将将q的首元素提取出并加入的首元素提取出并加入s1的栈顶的栈顶.b操作操作,将将s1的栈顶元素弹出并加入的栈顶元素弹出并加入q2的队列尾的队列尾.c操作操作,将将q的首元素提取出并加入的首元素

32、提取出并加入s2的栈顶的栈顶.d操作操作,将将s2的栈顶元素弹出并加入的栈顶元素弹出并加入q2的队列尾的队列尾.请判断请判断,是否可以经过一系列操作之后是否可以经过一系列操作之后,使得使得q2中依次存储着中依次存储着1,2,3,n.如果可以如果可以,求出字典序最小的一个操作序列求出字典序最小的一个操作序列.第35页，本讲稿共47页考虑单栈例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;第36页，本讲稿共47页定理定理：对于任意两个数定理：对于任意两个数qi和和qj来说来说,它们不能压入同一个栈中的充它们不能压

33、入同一个栈中的充要条件要条件p是是:存在一个存在一个k,使得使得ijk且且qkqiqi,这显然是不正确的这显然是不正确的.第37页，本讲稿共47页证明必要性：也就是必要性：也就是,如果两个数不可以压入同一个栈如果两个数不可以压入同一个栈,那么它们那么它们一定满足条件一定满足条件p.这里我们来证明它的逆否命题这里我们来证明它的逆否命题,也就是也就是如果如果不满足条件不满足条件p,那么这两个数一定可以压入同一个栈那么这两个数一定可以压入同一个栈.“不满足条件不满足条件p有两种情况有两种情况:一种是对于任意一种是对于任意ijk且且qiqi;另另一种是对于任意一种是对于任意iqj.第一种情况下第一种情

34、况下,很显然很显然,在在qk被压入栈的时候被压入栈的时候,qi已经被弹出栈已经被弹出栈.那么那么,qk不会对不会对qj产生任何影响产生任何影响(这里可能有点乱这里可能有点乱,因为看起来因为看起来,当当qjqK的时候的时候,是会有影响的是会有影响的,但实际上但实际上,这还需要另一个数这还需要另一个数R,满足满足JKR且且qrqjqk,也就是证明充分性的时候所说的情况也就是证明充分性的时候所说的情况而事实上我们现而事实上我们现在并不考虑这个在并不考虑这个r,所以说所以说qk对对qj没有影响没有影响).第二种情况下第二种情况下,我们可以发现这其实就是一个降序序列我们可以发现这其实就是一个降序序列,所

35、以所有数所以所有数字都可以压入同一个栈字都可以压入同一个栈.这样这样,原命题的逆否命题得证原命题的逆否命题得证,所以原命题得证所以原命题得证.此时此时,条件条件p为为qi和和qj不能压入同一个栈的充要条件也得证不能压入同一个栈的充要条件也得证.第38页，本讲稿共47页构图构图这样这样,我们对所有的数对我们对所有的数对(i,j)满足满足1=ij=n,检查是否存在检查是否存在ijk满足满足qkqiqj.如果存在如果存在,那么在点那么在点i和点和点j之间之间连一条无向边连一条无向边,表示表示qi和和qj不能压入同一个栈不能压入同一个栈.二分图的两部分看作两个栈二分图的两部分看作两个栈,因为二分图的同

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

37、结点染色为染色为1对应当前结点被压入对应当前结点被压入s1,为为2对应被压入对应被压入s2.为了字典为了字典序尽量小序尽量小,我们希望让编号小的结点优先压入我们希望让编号小的结点优先压入s1.又发现二分图的不同连通分量之间的染色是互不影响的又发现二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取一个未染色的编号最小的结点所以可以每次选取一个未染色的编号最小的结点,将它染将它染色为色为1并从它开始并从它开始DFS染色染色,直到所有结点都被染色为止直到所有结点都被染色为止.这样这样,我们就得到了每个结点应该压入哪个栈中我们就得到了每个结点应该压入哪个栈中。还有一点小问题还有一点小问题,就

38、是如果对于数对就是如果对于数对(i,j),都去枚举检查是都去枚举检查是否存在否存在k，使得，使得qkqIM第40页，本讲稿共47页最优乘车（最优乘车（NOI97）一名旅客最近到一名旅客最近到H城旅游，他很想去城旅游，他很想去S公园游玩，但如果从公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达他所在的饭店没有一路巴士可以直接到达S公园，则他可公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士路巴士,这样换乘几次后到达这样换乘几次后到达S公园。公园。现在用整数现在用整数1，2，N给给H城的所有的巴士站编号，约定这城的所有的巴

39、士站编号，约定这名旅客所在饭店的巴士站编号为名旅客所在饭店的巴士站编号为1，2，S，公园巴士站的，公园巴士站的编号为编号为N。写一个程序，帮助这名旅客寻找一个最优乘车方案写一个程序，帮助这名旅客寻找一个最优乘车方案,使他使他在从饭店乘车到在从饭店乘车到S公园的过程中换车的次数最少。公园的过程中换车的次数最少。输入输入N和和M条公交线路信息条公交线路信息求最少换车的次数求最少换车的次数第41页，本讲稿共47页模型的构建我们来分析样例我们来分析样例3767473621356747362135第42页，本讲稿共47页考察考察4736这条线路。由于巴士在同一线路上这条线路。由于巴士在同一线路上行走不需

40、换车，我们可设行走不需换车，我们可设47，43，46，73，76，36这些边的权值都为这些边的权值都为1。对每条线路我。对每条线路我们都这样构图，然后问题就转化成求起点们都这样构图，然后问题就转化成求起点1到终点到终点n的最短路。的最短路。第43页，本讲稿共47页01串问题（串问题（NOI99试题）试题）给定给定7个整数个整数N,A0,B0,L0,A1,B1,L1，要求设计一个，要求设计一个01串串S=s1s2sisN，满足：满足：（1）si=0或或si=1，1=i=N；（2）对于）对于S的任何连续的长度为的任何连续的长度为L0的子串的子串sjsj+1sj+L0-1(1=j=N-L0+1)，0

41、的个数大于等于的个数大于等于A0且小于等于且小于等于B0;（3）对于）对于S的任何连续的长度为的任何连续的长度为L1的子串的子串sjsj+1sj+L1-1(1=j=N-L1+1)，1的个数大于等于的个数大于等于A1且小于等于且小于等于B1;例如，例如，N=6,A0=1,B0=2,L0=3,A1=1,B1=1,L1=2，则存在一个满足上述所，则存在一个满足上述所有条件的有条件的01串串S=010101。输入：输入：N,A0,B0,L0,A1,B1,L1（3=N=1000）输出：一个满足所有条件的输出：一个满足所有条件的01串。串。第44页，本讲稿共47页构图（1）图的节点图的节点用用Ci表示表示

42、s1,s2.si中中1的个数，我们可以得到的个数，我们可以得到C1,C2.Cn，用他们作图，用他们作图的节点，将的节点，将C0也考虑进去（显然：也考虑进去（显然：C0=0），我们就得到了），我们就得到了N+1个个节点。节点。（2）图的边与权。若我们已找到一个串）图的边与权。若我们已找到一个串S，则这个串，则这个串S必须满足必须满足如下性质：对任意的如下性质：对任意的i，Ci一定符合下面的不等式：一定符合下面的不等式：第45页，本讲稿共47页样例构图样例构图输入：输入：6123112输出：输出：010101第46页，本讲稿共47页模型求解（1）判断是否有解判断是否有解考虑下面这样一种情况：考虑下

43、面这样一种情况：若若x+y+z0则则CiCi这显然是不可能得到的，所以若是出现了这种情况，则说明无这显然是不可能得到的，所以若是出现了这种情况，则说明无解。解。这种情况就是构建的图中出现负权回路的情况这种情况就是构建的图中出现负权回路的情况！（2）求出）求出S序列序列要求出要求出S序列，我们只要求出序列，我们只要求出C数组就可以了。因为数组就可以了。因为C数组和数组和S序列是一序列是一一对应的关系。而一对应的关系。而C数组的值，又可以通过构建的图论模型来求。数组的值，又可以通过构建的图论模型来求。图图中中C0节点到各个节点的最短距离，就是各个节点的值节点到各个节点的最短距离，就是各个节点的值。由于有。由于有负权，我们可以选择负权，我们可以选择Bellman-Ford算法。算法。第47页，本讲稿共47页