资源描述：
《NOI导刊 图论模型的构建.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、图论模型的构建长沙市雅礼中学朱全民NOIP若干图论的考题Core(2007):图的多源最短路算法及其简单处理双栈排序(2008):栈的应用+二分图的搜索最优贸易(2009):基本图论问题：求网线线序网线从机房连接到办公室在机房，所有网线从左到右编号为1,2,3,…,N给出每两条线是否交叉的信息，请计算办公室内从左到右各条线的编号选址问题现准备在n个居民点v1,v2,…,vn中设置一银行.问设在哪个点,可使最大服务距离最小?若设置两个银行,问设在哪两个点?模型假设假设各个居民点都有条件设置银行,并有
2、路相连,且路长已知.模型建立与求解用Floyd算法求出任意两个居民点vi,vj之间的最短距离,并用dij表示.⑴设置一个银行,银行设在vi点的最大服务距离为求k,使即若设置一个银行,则银行设在vk点,可使最大服务距离最小.⑵设置两个银行,假设银行设在vs,vt点使最大服务距离最小.记则s,t满足：进一步,若设置多个银行呢？求k,使即若设置一个银行,则银行设在vk点,可使最大服务距离最小.⑵设置两个银行,假设银行设在vs,vt点使最大服务距离最小.记则s,t满足：进一步,若设置多个银行呢？最优贸易某
3、国有M个城市N条道路，任意两个城市有道路，有一部分道路为单行线，一部分为双向道路。某人去该国旅游，从城市1出发到城市n结束，他想做水晶球的生意一次挣点旅行费用，每个城市有一个水晶球的价格（买入卖出都一样），他可以经过每个城市多次。问他能挣最多的费用为多少？如下图，假设城市1~5的价格为4，3，5，6，1则选择1-4-5-4-5路线，挣得5分析这是一道非常典型的图论题,如果有扎实的图论基础解决起来并不困难.解决这道题的关键是发现,我们可以将原图中的任意一个强连通分量收缩为一个点,这个新点的买入价格等
4、于该强连通分量中最小的买入价格,这个新点的卖出价格等于该强连通分量中最大的卖出价格.这是因为,这个新点的性质和一个强连通分量是一样的,如果我们要在一个强连通分量中进行购买操作,一定会选择买入价格最小的那个点,如果我们要在一个强连通分量中进行卖出操作,也一定会选择卖出价格最大的那个点.分析所以算法就非常清晰了.首先利用DFS将所有的强连通分量收缩,这样我们就可以得到一个有向无环图G.由于G中没有环,我们可以对G进行拓扑排序,然后利用递推求得到达某个点i时,可能的最低买入价格best(i)是多少,以及
5、该点最终能否到达终点.最后对于所有能够到达终点的点p,设其卖出价格为sell(p),在sell(p)-best(p)中取最大值即得到答案.时间复杂度仅为O(V+E).在实现的时候最好使用栈消除DFS中的递归调用,因为图中的点可以达到100000,当递归深度达到这么大的时候有相当大的几率发生栈溢出.参考实现中采用了非递归实现DFS.奇怪的电梯大楼的每一层楼都可以停电梯，而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个
6、数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：33125代表了Ki(K1=3,K2=3,……)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？输入：二行，第一行为三个用空格隔开的正整数，表示N,A,B(1≤N≤200,1≤A,B≤N)，第二行为N个用空格隔开的正整数，表示Ki。输出：仅一行，即最少按键次数,若无法到达，则输出-1。构图LIFT.IN51533125LIFT.OUT3对于A楼而言，实际上对它最多只能做2个
7、操作，上到A+X层或下到A-X层，当然前提是存在A+X或A-X层。显然，如果把每一层楼看做一个顶点，如果A楼可以到B楼，则从顶点A引一条到顶点B的边，这样一来，问题就变成了图论中的两顶点间最短路径问题了！当然权设为1就行了。人穿柱子游戏在一个无限长的条形路上，有n(n<=200)个柱子，体积不计，有一个人想从左边走到右边，人近似看成一个半径为R的圆（如下图），问能否实现？构图每个圆的大小完全相同，不存在包含，相切（如果内切，就是重合了，如果外切，就是中间不连通的）等等复杂的关系，只有相交和相离的关
8、系，而且如果2个圆之间相交的话，那么这2个圆就是相通的，可以在这2个圆的圆心之间连一条边，增加一个源点，与上边有交点的圆和源点连一条边，增加一个汇点，与下边有交点的圆和汇点连一条边，这样就把一道几何题完全转换成了一道图论题，只要判断源点和汇点之间是否有路就可以了奇怪的数列编程输入3个整数n，p，q，寻找一个由整数组成的数列（a1，a2，……，an），要求：其中任意连续p项之和为正数，任意连续q项之和为负数。0
