信息学奥赛一本通第4章第7节拓扑排序与关键路径(C++版)

1、第七节第七节 拓扑排序与关键路径拓扑排序与关键路径引入AOV网 在日常生活中，一项大的工程可以看作是由若干个子工程（这些子工程称为“活动” ）组成的集合，这些子工程（活动）之间必定存在一些先后关系，即某些子工程（活动）必须在其它一些子工程（活动）完成之后才能开始，我们可以用有向图来形象地表示这些子工程（活动）之间的先后关系，子工程（活动）为顶点，子工程（活动）之间的先后关系为有向边，这种有向图称为“顶点活动网络” ，又称“AOV网” 。123567894引入在AOV网中，有向边代表子工程（活动）的先后关系，我们把一条有向边起点的活动成为终点活动的前驱活动，同理终点的活动称为起点活动的后继活动。

2、而只有当一个活动全部的前驱全部都完成之后，这个活动才能进行。例如在上图中，只有当工程1完成之后，工程2、3、4、5、6才能开始进行。只有当2、3、4全部完成之后，7才能开始进行。一个AOV网必定是一个有向无环图，即不应该带有回路。否则，会出现先后关系的自相矛盾。1234上图就是一个出现环产生自相矛盾的情况。4是1的前驱，想完成1，必须先完成4。3是4的前驱，而2是3的前驱，1又是2的前驱。最后造成想完成1，必须先完成1本身，这显然出现了矛盾。拓扑排序算法 拓扑排序算法，只适用于AOV网（有向无环图）。把AOV网中的所有活动排成一个序列， 使得每个活动的所有前驱活动都排在该活动的前面，这个过程称

3、为“拓扑排序”，所得到的活动序列称为“拓扑序列”。一个AOV网的拓扑序列是不唯一的，例如下面的这张图，它的拓扑序列可以是：ABCDE，也可以是ACBDE，或是ADBCE。在下图所示的AOV网中，工程B和工程C显然可以同时进行，先后无所谓；但工程E却要等工程B、C、D都完成以后才能进行。ABCED构造拓扑序列可以帮助我们合理安排一个工程的进度，由AOV网构造拓扑序列具有很高的实际应用价值。算法思想：构造拓扑序列的拓扑排序算法思想很简单：选择一个入度为0的顶点并输出然后从AOV网中删除此顶点及以此顶点为起点的所有关联边；重复上述两步，直到不存在入度为0的顶点为止。若输出的顶点数小于AOV网中的顶点

4、数，则输出“有回路信息”，否则输出的顶点序列就是一种拓扑序列从第四步可以看出，拓扑排序可以用来判断一个有向图是否有环。只有有向无环图才存在拓扑序列。拓扑排序算法 算法实现： a) 数据结构：indgri: 顶点i的入度; stack : 栈 b) 初始化:top=0 (栈顶指针置零) c) 将初始状态所有入度为0的顶点压栈 d) I=0 (计数器) e) while 栈非空(top0) i. 栈顶的顶点v出栈；top-1; 输出v；i+； ii. for v的每一个后继顶点u 1. indgru-; u的入度减1 2. if （u的入度变为0） 顶点u入栈 f) 算法结束这个程序采用栈来找出入

5、度为0的点，栈里的顶点，都是入度为0的点。我们结合上图详细讲解：ABCD开始时，只有A入度为0，A入栈。栈：A拓扑排序算法 BCD栈顶元素A出栈并输出A，A的后继B、C入度减1，相当于删除A的所有关联边栈：空拓扑序列：ABCDB、C的入度都变成0，依次将B、C入栈。栈：BC（入栈顺序不唯一）拓扑序列：A拓扑排序算法 BD栈顶元素C出栈并输出C，C的后继D入度减1栈：B拓扑序列：ACD栈顶元素B出栈并输出B，B的后继D入度再减1。这时D入度为0，入栈。栈：D拓扑序列：ACB拓扑排序算法 D栈顶元素D出栈并输出D。栈空，结束栈：空拓扑序列：ACBD（不唯一）简单&高效&实用的算法。上述实现方法复杂

6、度O(V+E)。拓扑排序算法 【例4-12】、家谱树【问题描述】 有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。 给出每个人的孩子的信息。 输出一个序列，使得每个人的后辈都比那个人后列出。【输入格式】 第1行一个整数N（1=N=100），表示家族的人数。 接下来N行，第I行描述第I个人的儿子。 每行最后是0表示描述完毕。【输出格式】 输出一个序列，使得每个人的后辈都比那个人后列出。 如果有多解输出任意一解。【输入样例】 5 0 4 5 1 0 1 0 5 3 0 3 0【输出样例】 2 4 5 3 1拓扑排序算法 【参考程序】/gentree#include#includeusin

7、g namespace std;int a101101,c101,r101,ans101;int i,j,tot,temp,num,n,m;int main() freopen(gentree.in,r,stdin); freopen(gentree.out,w,stdout); cin n; for (i = 1; i j; if (j !=0 ) ci+; /ci用来存点i的出度 aici = j; rj+; /ri用来存点i的入度。 while (j != 0); 拓扑排序算法 for (i = 1; i = n; i+) if (ri = 0) ans+tot = i; /把图中所有入

8、度为0的点入栈，栈用一维数组ans表示 do temp = anstot; cout temp ; tot-;num+; /栈顶元素出栈并输出 for (i = 1; i = ctemp; i+) ratempi-; if (ratempi = 0) /如果入度减1后变成0，则将这个后继点入栈 ans+tot = atempi; while (num != n); /如果输出的点的数目num等于n，说明算法结束 return 0;拓扑排序算法 【例4-13】奖金【问题描述】由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。

9、公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。 【输入格式】第一行两个整数n,m，表示员工总数和代表数；以下m行，每行2个整数a,b，表示某个代表认为第a号员工奖金应该比第b号员工高。 【输出格式】若无法找到合理方案，则输出“Poor Xed”；否则输出一个数表示最少总奖金。【输入样例】2 11 2【输出样例】201拓扑排序算法 【数据规模】80的数据满足n=1000，m=2

10、000；100的数据满足n=10000，m=20000。【算法分析】首先构图，若存在条件“a的钱比b多”则从b引一条有向指向a；然后拓扑排序，若无法完成排序则表示问题无解（存在圈）；若可以得到完整的拓扑序列，则按序列顺序进行递推： 设fi表示第i个人能拿的最少奖金数； 首先所有fi=100（题目中给定的最小值）； 然后按照拓扑顺序考察每个点i，若存在有向边(j,i)，则表示fi必须比fj大，因此我们令fi = Max fi , fj+1 即可； 递推完成之后所有fi的值也就确定了，而答案就等于f1+fn。拓扑排序算法 【参考程序】#includeusing namespace std;int

11、a10001301=0,into10001,ans10001,m,n,money;void init() /读入数据，并构建图，统计入度 int i,x,y; cinnm; for(i=1;ixy; ay0+; /记录由y引出边的数目 ayay0=x; /记录由ay0引出边的顶点 intox+; /统计入度 bool topsort() /拓扑排序 int t,tot,k,i,j; tot=0;k=0; while(totn) /tot顶点个数 t=0; /用来判断有无环 for(i=1;i=n;i+) if(intoi=0) 拓扑排序算法 tot+;t+;money+=100; anst=i

12、; intoi=0 xfffffff; if(t=0)return false; /存在环 money+=k*t;k+; for(i=1;i=t;i+) /去掉相连的边 for(j=1;j=aansi0;j+)intoaansij-; return true;int main() init();money=0; if(topsort()coutmoneyendl; else coutPoor Xedendl; return 0;关键路径 利用AOV网络，对其进行拓扑排序能对工程中活动的先后顺序作出安排。但一个活动的完成总需要一定的时间，为了能估算出某个活动的开始时间，找出那些影响工程完成时间的

13、最主要的活动，我们可以利用带权的有向网，图中的边表示活动，边上的权表示完成该活动所需要的时间，一条边的两个顶点分别表示活动的开始事件和结束事件，这种用边表示活动的网络，称为“AOE网”。其中，有两个特殊的顶点（事件），分别称为源点和汇点，源点表示整个工程的开始，通常令第一个事件（事件1）作为源点，它只有出边没有入边；汇点表示整个工程的结束，通常令最后一个事件（事件n）作为汇点，它只有入边没有出边；其余事件的编号为2到n-1。在实际应用中，AOE网应该是没有回路的，并且存在唯一的入度为0的源点和唯一的出度为0的汇点。下图表示一个具有12个活动的AOE网。图中有8个顶点，分别表示事件0到7，其中，

14、0表示开始事件，7表示结束事件，边上的权表示完成该活动所需要的时间。关键路径 AOE网络要研究的问题是完成整个工程至少需要多少时间？哪些活动是影响工程进度的关键？下面先讨论一个事件的最早发生时间和一个活动的最早开始时间。如下图，事件Vj必须在它的所有入边活动eik（1kn）都完成后才能发生。活动eik（1kn）的最早开始时间是与它对应的起点事件Vik的最早发生时间。所有以事件Vj为起点事件的出边活动ejk（1km）的最早开始时间都等于事件Vj的最早发生时间。所以，我们可以从源点出发按照上述方法，求出所有事件的最早发生时间。关键路径 设数组earliest1.n表示所有事件的最早发生时间，则我们

15、可以按照拓扑顺序依次计算出earliestk：earliest1=0earliestk=maxearliestj+dutjk (其中，事件j是事件k的直接前驱事件，dutjk表示边上的权)对于上图，用上述方法求earliest0.7的过程如下：earliest0=0earliest1=earliest0+dut01=0+6=6earliest2=earliest0+dut02=0+7=7earliest4=maxearliest1+dut14，earliest2+dut24=max6+5,7+4=11earliest3=maxearliest1+dut13，earliest4+dut43=ma

16、x6+3,11+3=14earliest5=maxearliest3+dut35，earliest4+dut45=max14+2,11+4=16earliest6=earliest4+dut46=11+3=14earliest7=maxearliest3+dut37，earliest5+dut57, earliest6+dut67=max14+5,16+2,14+4=19关键路径 最后得到的earliest7就是汇点的最早发生时间，从而可知整个工程至少需要19天完成。但是，在不影响整个工程按时完成的前提下，一些事件可以不在最早发生时间发生，而向后推迟一段时间，我们把事件最晚必须发生的时间称为该

17、事件的最迟发生时间。同样，有些活动也可以推迟一段时间完成而不影响整个工程的完成，我们把活动最晚必须开始的时间称为该活动的最迟开始时间。一个事件在最迟发生时间内仍没发生，或一个活动在最迟开始时间内仍没开始，则必然会影响整个工程的按时完成。事件Vj的最迟发生时间应该为：它的所有直接后继事件Vjk（1km）的最迟发生时间减去相应边上的权（活动ejk需要时间），取其中的最小值。且汇点的最迟发生时间就是它的最早发生时间，再按照逆拓扑顺序依次计算出所有事件的最迟发生时间，设用数组lastest1.n表示，即：lastestn=earliestnlastestj=minlastestk-dutjk (其中，

18、事件k是事件j的直接后继事件，dutj,k表示边上的权)对于上图，用上述方法求lastest 0.7的过程如下：lastest7=earliest7=19lastest6=lastest7-dut67=19-4=15lastest5=lastest7-dut57=19-2=17lastest3=minlastest5-dut35，lastest7-dut37 =min17-2,19-5 =14关键路径 lastest4=minlastest3-dut43，lastest5-dut45, lastest6-dut46 =min14-3,17-4,15-3 =11lastest2=lastest4

19、-dut24=11-4=7lastest1=minlastest3-dut13，lastest4-dut14 =min14-3,11-5 =6lastest0=minlastest1-dut01，lastest2-dut02 =min6-6,7-7 =0计算好每个事件的最早和最迟发生时间后，我们可以很容易地算出每个活动的最早和最迟开始时间，假设分别用actearliest和actlastest数组表示，设活动i的两端事件分别为事件j和事件k,如下所示：活动i事件j 事件k则：actearliesti=earliestjactlastesti=lastestk-dutjk关键路径 对于上图，用上

20、述方法求得所有活动的最早和最迟开始时间如下表：活动活动 21 1424353743454 5 6 最早最早0 00 06 66 67 71414141411111111111116161414最迟最迟0 00 011116 67 71515141411111313121217171515余量余量0 00 05 50 00 01 10 00 02 21 11 11 1 上表中的余量（称为开始时间余量）是该活动的最迟开始时间减去最早开始时间，余量不等于0的活动表示该活动不一定要在最早开始时间时就进行，可以拖延一定的余量时间再进行，也不会影响整个工程的完成。而余量等于0的活动必须在最早开始时间时进行

21、，而且在规定的工期内完成，否则将影响整个工程的完成。我们把开始时间余量为0的活动称为“关键活动”，由关键活动所形成的从源点到汇点的每一条路径称为“关键路径”。关键路径 上图所示的AOE网的关键路径如下图所示。细心的读者可能已经发现，其实关键路径就是从源点到汇点具有最大路径长度的那些路径。这很容易理解，因为整个工程的工期就是按照最长路径计算出来的。很显然，要想缩短整个工程的工期，就应该想法设法去缩短关键活动的持续时间。读者可以根据上面的思想编程求出AOE网的关键路径。上机练习 1、烦人的幻灯片【问题描述】李教授将于今天下午作一次非常重要的演讲。不信的事他不是一个非常爱整洁的人，他把自己演讲要用的

22、幻灯片随便堆在了一起。因此，演讲之前他不得不去整理这些幻灯片。作为一个讲求效率的学者，他希望尽可能简单地完成它。教授这次演讲一共要用n n张幻灯片（n=26n=26），这n n张幻灯片按照演讲要使用的顺序已经用数字1n1n编了号。因为幻灯片是透明的，所以我们不能一下子看清每一个数字所对应的幻灯片。现在我们用大写字母A,B,CA,B,C再次把幻灯片依次编号。你的任务是编写一个程序，把幻灯片的数字编号和字母编号对应起来，显然这种对应应该是唯一的；若出现多种对应的情况或是某些数字编号和字母编号对应不起来，我们称对应是无法实现的。【输入格式】文件的第一行只有一个整数n n，表示有n张幻灯片，接下来的n n行每行包括4 4个整数xmin,xmax,ymin,ymaxxmin,xmax,ymin,ymax（整数之间用空格分开）为幻灯片的坐标，这n n张幻灯片按其在文件中出现的顺序从前到后依次编号为A,B,CA,B,C，再接下来的n行依次为n n个数字编号的坐标x,yx,y，显然在幻灯片之外是不会有数字的。【输出格式】若是对应可