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

分析 这是一道非常典型的图论题, 如果有扎实的图论基础解决起来并不困难. 解决这道题的关键是发现, 我们可以将原图中的任意一个强连通分量收缩为一个点, 这个新点的买入价格等于该强连通分量中最小的买入价格, 这个新点的卖出价格等于该强连通分量中最大的卖出价格. 这是因为, 这个新点的性质和一个强连通分量是一样的, 如果我们要在一个强连通分量中进行购买操作, 一定会选择买入价格最小的那个点, 如果我们要在一个强连通分量中进行卖出操作, 也一定会选择卖出价格最大的那个点. ? 分析 所以算法就非常清晰了. 首先利用DFS将所有的强连通分量收缩, 这样我们就可以得到一个有向无环图G. 由于G中没有环, 我们可以对G进行拓扑排序, 然后利用递推求得到达某个点i时, 可能的最低买入价格best(i)是多少, 以及该点最终能否到达终点. 最后对于所有能够到达终点的点p, 设其卖出价格为sell(p), 在sell(p)-best(p)中取最大值即得到答案. 时间复杂度仅为O(V+E). ? 在实现的时候最好使用栈消除DFS中的递归调用, 因为图中的点可以达到100000, 当递归深度达到这么大的时候有相当大的几率发生栈溢出. 参考实现中采用了非递归实现DFS. 奇怪的电梯 大楼的每一层楼都可以停电梯，而且第i层楼(1=i=N)上有一个数字Ki(0=Ki=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,……)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？ 输入： 二行，第一行为三个用空格隔开的正整数，表示N,A,B(1≤N≤200, 1≤A,B≤N)，第二行为N个用空格隔开的正整数，表示Ki。 输出：仅一行，即最少按键次数,若无法到达，则输出-1。 构图 LIFT.IN 5 1 5 3 3 1 2 5 LIFT.OUT 3 对于A楼而言，实际上对它最多只能做2个操作，上到A+X层或下到A-X层，当然前提是存在A+X或A-X层。显然，如果把每一层楼看做一个顶点，如果A楼可以到B楼，则从顶点A引一条到顶点B的边，这样一来，问题就变成了图论中的两顶点间最短路径问题了！当然权设为1就行了。 ? 人穿柱子游戏 在一个无限长的条形路上，有n(n=200)个柱子，体积不计，有一个人想从左边走到右边，人近似看成一个半径为R的圆（如下图），问能否实现？ 构图 每个圆的大小完全相同，不存在包含，相切（如果内切，就是重合了，如果外切，就是中间不连通的）等等复杂的关系，只有相交和相离的关系，而且如果2个圆之间相交的话，那么这2个圆就是相通的，可以在这2个圆的圆心之间连一条边，增加一个源点，与上边有交点的圆和源点连一条边，增加一个汇点，与下边有交点的圆和汇点连一条边，这样就把一道几何题完全转换成了一道图论题，只要判断源点和汇点之间是否有路就可以了 奇怪的数列 编程输入3个整数n，p，q，寻找一个由整数组成的数列（a1，a2，……，an），要求：其中任意连续p项之和为正数，任意连续q项之和为负数。0n100，0p，qn，若不存在这样的整数数列，则输出NO；否则输出满足条件的一个数列即可。 输入格式： 仅一行分别表示n，p，q，之间用一个空格隔开。? 输出格式： 只有一行，有解即输出这个数列，每个数之间用一个空格隔开。否则输出NO。 分析 如果我们按常规思想，直接将第i个整数ai开始的k个整数之和描述成多项式ai+ai+1+…+ai+k-1的话，问题就很难再往下思考和解决了。所以，我们不防换个角度，暂且撇去每一项数究竟为何值的具体细节，而将注意力集中至连续性这一特点上。设si表示数列前i个整数之和，即si=a1+a2+…+ai。其中s0=0 (0≤i≤n)。显然根据题意，有： sisi+p (0≤i≤n-p) si+qsi (0≤i≤n-q) 下面，我们把每个si抽象成一个点，则根据上述两个不等式可以建立一个有向图，图中共有n+1个顶点，分别为s0，s1，……，sn。若sisj(0≤i，j≤n)，则从si往sj引出一条有向边。 构图 对于n=6，p=5，q=3的情况，我们可以建立下图： 对图进行拓扑排序； if 图有回路 then 无解退出 else 生成拓扑序列order[0]…order[n]； 那么如果得到了一个拓扑序列，该如何转换成s数组呢？因为拓扑序列中顶点对应的s值是递减的，其中s0=0。 如果order[i]=0，则依次设