图的应用(王建德)

1、图型问题的图型问题的解题策略解题策略图的的定义图的的定义 如果数据元素集合D中的各元素之间存在任意的前后件关系R，则此数据结构G=（D，R）称为图。如果将数据元素抽象为结点，元素之间的前后件关系用边表示，则图亦可以表示为G=（V，E），其中V是结点的有穷（非空）集合，E为边的集合。如果元素a是元素b的前件，这种前后件关系对应的边用(a，b)表示，即(a，b)E。 现实生活中的许多问题可以转化为图,并可以借助图论的经典算法解决。 图的遍历图的遍历 给出一个图给出一个图G G和其中任意一个结点和其中任意一个结点V V0 0，从，从V V0 0出发系统地访问出发系统地访问G G中所有结点，每一个结点

2、被访问一次，这就叫图的遍历。中所有结点，每一个结点被访问一次，这就叫图的遍历。遍历图的结果是按访问顺序将结点排成一个线性序列。遍历图的算法是求解图的连通性问题、拓朴排序和求关键路径等算法的基础。通常有两种遍历方法： 深度优先搜索（dfs） 广度优先搜索(bfs) 它们对无向图和有向图都适用。我们以相邻矩阵存储结构给出深度优先搜索和广度优先搜索的程序。深度优先搜索深度优先搜索 深度优先搜索类似于树的前序遍历，是树的前序遍历的推广。其搜索过程如下： 假设初始时所有结点未曾被访问。深度优先搜索从某个结点V0出发，访问此结点。然后依次从V0的未被访问的邻接点出发深度优先遍历图，直至图中所有和V0有路径

3、相连的结点都被访问到。若此时图中尚有结点未被访问，则另选一个未曾访问的结点作起始点，重复上述过程，直至图中所有结点都被访问为止。换句话说，深度优先搜索遍历图的过程是以深度优先搜索遍历图的过程是以V V0 0为起始点，由左为起始点，由左而右，依次访问由而右，依次访问由V V0 0出发的每条路径。出发的每条路径。 从v3出发，按深度优先搜索的顺序遍历，得到的结点序列是v3v2v1v5v4。 调用一次dfs(i)，可按深度优先搜索的顺序访问处理结点i所在的连通分支（或强连通分支）。整个图按深度优先搜索顺序遍历的过程如下：注意注意 1、将原问题转化为图 2、尽可能在搜索前计算出初始解和约束条件借助的变

4、量值（初始化工作） 3、准确定义搜索的状态、搜索范围和约束条件交易交易在n个城市间连接了m条道路，连接每条道路的两个城市间可进行一次交易，产生一定的收益。请设计一个能产生最大经济效益的交易方案。输入：城市数n(1n100)和道路数m(m0)；以下有m行，每行为“i j v”表示城市i和城市j之间进行一次交易的收益为v；输出：n个整数。与城市i进行一次交易的城市序号为其中第i个整数；如果没有城市与城市i进行交易，则第i个整数为0。数据类型数据类型var n,m,i,j,k,n0,a,b:integer; g:array1.max,1.maxof real;无向有权图 bt,w,aw:real;

5、bt为最大经济效益 hv:array1.maxof real; 每个城市的交易量 vt:array1.maxof boolean;未交易标志 ans,bans:array1.maxof byte; bans为最佳交易方案，其中bansi为与城市i进行一次交易的城市序号；ans 为当前交易方案1、预处理、预处理1、以城市为顶点、道路为边、收益为边权构造图的相邻矩阵g2、计算可交易量的初始值aw(=g(a,b)(a,b)E)3、按照有序要求计算每个顶点的出弧的权和hi(=g(i,j)i+1jn,(i,j)E)3、用贪心法计算最大经济效益bt和交易方案bans的初始值(在所有出边中选择收益最大的城市

6、交易) 贪心计算最大经济效益贪心计算最大经济效益bt bt和交易方案和交易方案bansbans的初始值的初始值 inc(n); for i:=1 to n-1 do gi,n:=0; bt:=0; 最大经济效益初始化 fillchar(vt,sizeof(vt),0); fillchar(bans,sizeof(bans),0);每个城市的交易对象初始化 for i:=1 to n-1 do搜索每一个未交易城市i if not vti then begin k:=0;在与城市i相连的未交易城市里选择交易量最大的城市k for j:=i+1 to n do if not vtj and (k=0

7、) or (gi,jgi,k)then k:=j; if (k0) and (gi,k=0)若城市k存在，则设定城市i与城市k交易，交易量记入经济效益 then begin bt:=bt+gi,k; bansi:=k; bansk:=i; vtk:=true end end;2、递归计算最大经济效益和交易方案、递归计算最大经济效益和交易方案状态状态(nw(nw，lglg）：）：当前考察的城市now和最大可交易量lg。实际上ans和vt亦为状态，但由于其存储量大，因此作为全局变量。初始状态为（1,aw）；边界条件边界条件lg=bt:lg=bt:当前方案不可能更优目标状态目标状态vtnwvtnw和

8、和nw=n+1nw=n+1：若城市nw已确定交易对象，则递归子状态（nw+1,lg）若每个城市的交易对象已确定，则记下经济效益lg和交易表ans搜索范围搜索范围nw+1innw+1in：在未交易的城市中搜索与城市nw相连的城市i，城市i和城市nw交易，并递归子状态（nw+1,lg-hvnw-hvi+gnw,i) procedure search(nw:integer;lg:real);从nw城市和交易量lg出发，递归计算最大经济效益bt和交易方案bans var i:integer;begin if lg=0) then begin ansnw:=i;ansi:=nw;vti:=true;城市

9、i和城市nw交易，并递归 search(nw+1,lg-hvnw-hvi+gnw,i); ansnw:=0;ansi:=0;vti:=false恢复递归前的状态 endend;主程序主程序输入信息，进行递归前的初始化；fillchar(vt,sizeof(vt),0);所有城市未交易fillchar(ans,sizeof(ans),0);当前交易标未空search(1,aw)；输出最大经济效益bt和交易方案bans；栅栏栅栏 农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木材店购买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买

10、这些木板，然后切割成他所需要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为10的木板可以切成长度为8和2的两个木板。 你的任务：给你约翰所需要的木板的规格，还有木材店老板能够给出的木材的规格，求约翰最多能够得到多少他所需要的木板。输入文件：输入文件：第一行为整数m(m=50)表示木材店老板可以提供多少块木材给约翰。紧跟着m行为老板提供的每一块木板的长度。接下来一行(即第m+2行)为整数n(n=1000)，表示约翰需要多少木材。接下来n行表示他所需要的每一块木板的长度。木材的规格小于32767。（对于店老板提供的对于店老板提供的和约翰需要的每块木板，你只能使用一

11、次和约翰需要的每块木板，你只能使用一次）。输出文件输出文件：约翰最多能够得到的符合条件的木板的个数。思维方向思维方向 计算木材店老板可提供的木板的长度和sum 按照长度递增的顺序排列各规格的木板。若前i-1个规格的长度和不大于sum，前i个规格的长度和大于sum，则老板切下的木板数不可能超过i。因此i是可切下的木板数上限。 在1ki的范围内，按照递增顺序计算切下k个规格的可行性。一旦确定不能切下k个规格，则k-1就是问题的解。多维背包问题多维背包问题: :搜索搜索+ +剪枝剪枝搜索状态：搜索状态：约翰是否能够得到dep块符合条件的木板。搜索顺序：搜索顺序：按照长度递减的顺序搜索规格，因为长的木

12、板比短的木板更难切。如果当前搜索的木板不能割下第dep个规格，则这个枝便可以剪去。避免重复搜索：避免重复搜索：对于两个有相同长度规格的木板，第一个规格从木材A上切下、第二个规格从木材B上切下和第一个规格从木材B上切下、第二个规格从木材A上切下的状态是同一种情况，造成了重复搜索。令Noa表示规格a从哪块木材切下。为了避免重复搜索，可以规定对于相同长度的规格a和b（arailj then begin tmp:=raili;raili:= railj; railj:=tmp;end; sum:=0;sum1:=0; for i := 1 to n do inc(sum, boardi);计算可提供的

13、木板长度总和 for i := 1 to m do begin估计上界 inc(sum1,raili); if sum1sum then begin up:=i; break;end; end; if up = 0 then up := m; ans := 1;限界深搜ID-DFS while (ans=up) and search(ans)search(ans) do inc(ans); writeln(ans-1);输出约翰得到的符合条件的最多木板数end.3 3、递归计算得到、递归计算得到depdep块符合条件块符合条件的木板的可行性的木板的可行性function search(dep:

14、integer) : boolean;若约翰能够得到dep块符合条件的木板，则返回true；否则返回falsevar i, down : byte;begin if dep=0 then begin search:=true;exit;end;找到一组解马上退出 for i := 1 to n do首先为木板选择长度相同的木材 if boardi=raildep then begin seldep:=i;boardi:=0; search := search(dep-1); boardi:=raildep;恢复 exit; end;if (depans)and(raildep=raildep

15、+ 1)seli记录第i块木板从哪块木材切下，如果i的长度和j的长度相同，i=j, 那么要保证seli=raildep若木块i能割下第dep个规格，则割下 then begin dec(boardi,raildep);seldep:=i; if search(dep-1)若能够得到dep1块符合条件的木板，则恢复割前状态，成功回溯 then begin inc(boardi,raildep);search:=true;exit; end; inc(boardi,raildep);恢复割前状态 end; search := false;约翰不能得到dep块符合条件的木板end;广度优先搜索广度优

16、先搜索 广度优先搜索类似于树的按层次遍历的过程，其搜索过程如下： 假设从图中某结点v0出发，在访问了v0之后依次访问v0的各个未曾访问的邻接点，然后分别从这些邻接点出发按广度优先搜索的顺序遍历图，直至图中所有可被访问的结点都被访问到。若此时图中尚有结点未被访问，则任选其中的一个作起始点，重复上述过程，直至图中所有结点都被访问到为止。换句话说，按广度优先顺序搜索遍历图的过程是以按广度优先顺序搜索遍历图的过程是以v v0 0为起始点，为起始点，由近及远，依次访问和由近及远，依次访问和v v0 0有路径相连且路径长度为有路径相连且路径长度为1 1，2 2，33的结点。的结点。 从v3出发按广度优先搜

17、索的顺序遍历，得到的结点序列是v3v2v4v1v5 由于队列“先进先出”的存取规则与广度优先搜索的遍历顺序相吻合，因此使用了一个工作队列q，按访问的先后顺序存储被访问过的结点序号。 fillchar(f, sizeof(f) , 0);访问标志初始化 fS :=true; q 1 := S;访问源点，源点入队 open := 1; closed := 1;队列的首尾指针初始化 while open = closed do若队列非空，则访问与队首元素相连的未访问点，计算其路径长度，并将它们送入队列 begin for i := 1 to N do if (fi =false)and(aqopen

18、,i0)or(qopeni) then begin 访问顶点I;fi:=true; inc(closed); qclosed := i; end; inc(open);出队 end;调用一次bfs(i)可按广度优先搜索的顺序访问处理结点i所在的连通分支（或强连通分支）。整个图按广度优先搜索顺序遍历的过程如下：宽度优先搜索的应用宽度优先搜索的应用 1、计算连通子图 2、计算无权图的单源最短路街道赛跑街道赛跑下图给出了一个沿街道赛跑的路线。图中有许多点，给以标号0，1，N(此图中N=9)，点之间可以用含箭头的线相连。标号为0的点是起点；标号为N的点为终点。含箭头的线表示单向通行的街道。运动员沿箭头

19、所指方向从一个点跑向另一个点；在每一个点上，运动员可以选择任何一个箭头(向外的)继续向前跑。 一个完整路线具有如下特点： 1路线中每一点都可从出发点到达； 2路线中每一点都可到达终点； 3终点处没有向外的箭头。 运动员要到达终点，但不要求路线(图)中的每一点都经过。但是路线(图)中的某些点是必经之点。上图的例子中，必经之点是：0，3，6，9。 任务任务A:A: 题目给出一个完整路线（图），请编程找出所有必经之点。请注意，输出必经之点时，应不包括起点和终点。任务任务B:B: 假定赛跑必须在相邻的2天来举行。因此，要把原来给定的完整路线（图）分成两个子路线（图）。第1天从点0出发，结束于“分裂点”

20、。第2天从“分裂点”出发，结束于点N。 题目给出一个完整路线（图）C，请编程输出所有可能的“分裂点”（任务B）。“分裂点”S一定不是起点或终点。C可被S分成两个完整的子路线：这两个子路线没有公共的箭头线，并且S是这两个子路线的唯一公共点。在上的例子中，仅点3是“分裂点”。输入数据输入数据：INPUTTXT描述一个完整路线（最多50个点，最多100个箭头），文件共（n1）行。前面n行（0（n-1）描述箭头的终点。第i行中的每一个数字表示从点i（0in1）出发的每一个箭头的终点。以2作为该行的结束。文件的最后一行（第n行）中有一个数字1，表示文件的结束。输出数据：输出数据：你的程序向输出文件OUT

21、PUTTXT写入两行数据，第1行表示必经点（子任务A）首先是必经点的总数，其后是必经点的标号，标号的顺序无关紧要。第2行表示“分裂点”：首先是分裂点的总数，其后是分裂点的标号，标号出现的先后顺序无关紧要（子任务B）。必经点和分裂点的特征 必经点必经点: :是指运动员从起点0出发，沿箭头方向跑，无论走哪条路线，都经由该点到达终点N。所有这些点组成必经点的集合。反之，在完整路线中去除必经点集合中的任一个点，无论运动员选择哪条路线跑，都不可能从起点0跑至终点N。分裂点分裂点: :运动员从起点0出发沿箭头方向跑，无论走哪条路线，都不约而同地走到某一个点上。而此时，所有从点0至该点路线上的点都不为余下的

22、任一点的箭头终点。在这种情况下，从该点出发可到达终点N。这个点即所谓分裂点。具体地讲，分裂点具有如下特征： 某点是必经点； 在完整路线中去除这个必经点后，由起点出发的运动员无论如何也不会跑到由这个必经点出发的任一箭头的终点； 完整路线中去除这个必经点后的所有点，分成两个互为独立的集合 可从出发点0到达。这些点组成子路径1； 无法从出发点0到达。这些点组成子路径2； 两个集合中的点之间，无任何箭头相连；满足上述3个条件的点为分裂点，所有这些点组成分裂点的集合。运算顺序运算顺序 分裂点是在必经点的基础上产生； 无论是判别必经点还是分裂点，都必须预先在完整路线中删除判别点； 顺序设点1、点2，点N1

23、为当前判别点。对于每一个判别点，先设删除标志、其余点未达标志（即未能从出发点到达）。然后判别是否可从出发点0到达终点N。若能够，则该点为非必经点；否则该点为必经点。若判别出该点是必经点，则再判别该点是否同时满足分裂点的特征2和特征3。若满足条件，则该点又是分裂点。 采用广度优先搜索的方法采用广度优先搜索的方法 从点0开始，按逐层搜索的方法对删除当前判别点后的路线重复进行访问，直至找不到可访问的点为止。广度搜索的结果，将路线上的所有点(除当前判别点外)分为两个集合： 广度优先搜索中访问到的点，即从出发点0可达的点集合，设这些点到达标志； 广度优先搜索中未访问过的点，即不可从出发点0到达的点集合。

24、这些点设未到达标志； 若终点N在第二个集合中，则当前判别点是必经点，然后再判别两个集合是否互为独立。若与必经点相连的所有点都在第二个集合中，且两个集合中的点之间无任何箭头相连，则这个必经点亦是分裂点。For i1 to n-1 do顺序设点1、点2，点N1为当前判别点Begin 删除顶点i，构建新图的相邻矩阵a； BFS(0)；宽度优先搜索出发点0可达的点集 if fn=false 若出发点0不可达终点n，则顶点i为必经点 Then begin 输出顶点i为必经点； Fundtrue；初始时假设顶点i为分裂点 For k0 to n-1 do搜索出发点0可达的点集合 For p0 to n d

25、o搜索出发点0不可达的点集合 if(fk=true)and(fp=false)and(ak,p0)or(ap,k0)Then begin Fundfalse;break;end;若两个点集间有边相连，则退出for循环 if Fund then输出顶点i为分裂点； End；thenEnd；for子图划分给定一个无向图，图中有一个起点S和一个终点T。要求选K个集合S1，S2，SK，每个集合都含有图中的一些边，任意两个不同的集合的交集为空。并且从图中任意去掉一个集合，S到T都没有通路。要求K尽量大。无解条件无解条件如果S到T在图中有一条长为L的最短路，那么显然答案不会超过L：如果答案大于L，那么根据

26、抽屉原理，必定至少有一个集合中没有这条路上的任意一条边。那么显然删去这个集合，S到T仍然连通：至少这条最短路没有被破坏。所以与题目要求不符，导致矛盾。构造构造K K= =L L的方案的方案如果S到T的最短路是L，则构造方法如下：首先求出S到任意一点u的最短路D(u)。这样对图上的任意一条边e=uv，如果D(v)-D(u) =1，且D(v)L，就将这条边加入集合SD(v)中。这样就构造出来一种分组方案。 为什么？为什么？证明证明 引理引理 如果图上的任意一条边e=uv，D(v)D(u) = 1且D(v)=ieSi。那么从图上将Si中的所有边删去，对原图上任意D(p)i的点p，在新图上S到p均无通

27、路。 证明证明 如果D(p)i，就说明任意一条从S到p的路径中至少包括D(p) + 1个点：S, p1, p2, , p，顺序写出S到每一个点最短路的长度：D(S), D(p1), D(p2), , D(p) (1)这个数列(1)一定以0开头，最后结尾是D(p) i，而根据最短路的性质，数列(1)中相邻两项差的绝对值一定不超过1，所以在这个数列中一定会出现相邻的两个数i-1，i。而显然对应的边在新图中被删去了，因此在新图中无法找到这条路径。于是，从图中删去Si的所有边，就可以保证S到p没有路径。因此，引理成立。定理 上文描述的构造集合的方案是正确的 证明证明 上文所说的任意Si（iL）满足引理

28、中的条件，因此删去任意Si（iL）后S到T：D(T)=Li，一定没有通路。所以这个构造集合的方案符合题意，是正确的。这样，编程实现就很简单了：图中每条边的长度都为1，求最短路数组的功能可以有宽度优先搜索实现。所以算法的时间、空间复杂度都是O(E)。数据结构数据结构Const Limit = 400;顶点数的上限 Maximum = 10000;Type Tdata = array1.Limit , 1.Limit of longint; Tvisited = array1.Limit of longint; Tqueue = array1.Limit of longint;Var data :

29、 Tdata;datai，j为边(I,j)的边序号 visited : Tvisited; visitedi为顶点i与s的最短路径长度，-1表示未访问 queue : Tqueue;队列 N , S , T : longint; 顶点数、源点、终点通过宽度优先搜索计算边集通过宽度优先搜索计算边集 fillchar(visited , sizeof(visited) , $FF);访问标志初始化 visitedS := 0; queue1 := S;访问源点，源点入队 open := 1; closed := 1;队列的首尾指针初始化 while open = closed do若队列非空，则访

30、问与队首元素相连的未访问点，计算其路径长度，并将它们送入队列 begin for i := 1 to N do if (visitedi=-1)and(dataqueueopen,i0) then begin visitedi:=visitedqueueopen+1; inc(closed);queueclosed:=i; end; inc(open);出队 end;输出集合个数和每个集合中的边信息输出集合个数和每个集合中的边信息writeln(visitedT);输出集合个数，即s到t的最短路径长度for i := 0 to visitedT - 1 do依次输出边集 begin tot :

31、= 0;计算由S出发的所有最短路径上的第i条边的条数tot ，这些边组成了集合si for j := 1 to N do if visitedj = i then for k :=1 to N do if(visitedk=i+1)and(dataj,k0) then inc(tot); write(tot);输出si集合中的边数 for j := 1 to N do输出si集合中的所有边 if visitedj = i then for k := 1 to N do if(visitedk=i+1)and(dataj,k0) then write( , dataj,k); writeln;

32、end; 计算无向图的传递闭包计算无向图的传递闭包【例题】计算连通性问题【例题】计算连通性问题输入一张无向图，指出该图中哪些顶点对之间有路。输入：输入：n (顶点数，1n20);e (边数1e210);以下e行，每行为有边连接的一对顶点输出：输出： k行，每行两个数，为存在通路的顶点对序号i、j(ij)无向图的传递闭包主要用于计算图的连通性和图中满足条件的连通分支。借鉴传递闭包的思想，可计算每一对顶点间的最短路径。判别任两个顶点之间是否有路判别任两个顶点之间是否有路var longlink：array1.20，1.20 of boolean； 无向图和无向图的传递闭包。其中 我们递推产生lon

33、glink(0)、longlink(1)、longlink(n)。在递推过程中，路径长度的+运算和比较大小的运算用相应的逻辑运算符and和or代替。对于i，j和k=1n，如果图中结点i至结点j间存在通路且通路上所有结点的序号均属于1k，则定义longlinkij(k)=1；否则longlinkij(k)=0。 longlinkij(k)=longlinkij(k-1)or(longlinkik(k-1)andlonglinkkj(k-1)传递闭包longlink的计算过程如下：for k1 to n do 枚举中间顶点 for i1 to n do枚举所有顶点对 for j1 to n do

34、计算顶点i和顶点j的连通情况 longlinki，jlonglinki，jor(longlinki，kandlonglinkk，j)；无路至有路至jijifalsetruejilonglink,主程序fillchar(longlink，sizeof(longlink)，0)；传递闭包初始化fillchar(link，sizeof(link)，0)；无向图初始化readln(n)；readln(e)；读顶点数和边数for k1 to e do输入无向图的信息,构造传递闭包的初始值 begin readln(i，j)； longlinki，jtrue；longlinkj，itrue； end；fo

35、r计算传递闭包longlink；for i1 to n-1 do输出所有存在通路的顶点对 for ji+1 to n do if longlinki，j then 输出i和j；应用应用1、传递闭包每一行（列）中值为ture的元素代表对应顶点所在的连通分量 顶点数最多的一个连通分支：对应含true最多的行 有向无圈图DAG的根r（r到其他任何顶点都有路）：r行元素值除r列外都为true；2、将布尔变量改为路径长度、将内循环的布尔表达式改为比较路径长短的数值表达式，即可求任一对顶点间的最长路和最短路。 有向无圈图DAG中最长路的长度：最长路矩阵中的最大值 带权有向图G的中心v(v是G的一个顶点，v

36、的偏心距定义为 ，偏心距最小的顶点即为G的中心：最长路矩阵中每行的最大元素对应于该顶点的偏心距。N行中偏心距最小的行对应于G的中心max的最短路长到从vwVw传递闭包的弊病传递闭包的弊病 1、有约束条件：求任一对顶点间的最长路时不能出现正权回路；求最短路时不能出现负权回路。 2、虽然编程简单，但时间效率低下。染色染色一个N个点的无向完全图，每条边都被染成1, M的一种颜色，要求选择一部分颜色，作为一个集合S，且S中的元素个数不超过div(m+1)/2) ，并满足如下性质： 图中任意两个点a和b，一定存在一条长度不大于3的通路，其每条边的颜色都属于S。一般情况：盲目枚举颜色数1颜色数 (m+1)

37、div 2 的所有可能组合,判断任两个顶点间长度不大于3的通路上的颜色是否属于当前组合。如果是，则该颜色组合即为问题解。显然，可能的颜色组合数多达 ，其计算量是根本无法承受的。 “极端情况”：将颜色1, M等分成两个元素数不超过的子集A和B。如果A和B中至少有一个集合满足成为S的条件，则问题可顺利解决。 211miimc证明这就是要证明A和B中至少有一个集合满足题目中的那条性质。设设A A不满足这条性质不满足这条性质, ,证明证明B B一定是满足性质的一定是满足性质的S S。考察任意一个不相等的点对(a, b)，如果(a, b)的颜色属于B，那么在B集合诱导的子图中a和b是直接相连的：即存在一

38、条长度不大于3的通路。否则，(a, b)的颜色属于A，那么假设边是A颜色与a相连的点集合为NA(a)，边是B颜色的点集为NB(a)；同理定义NA(b)和NB(b)。易知：NA(a)NB(a) = 1, N / aNA(b)NB(b) = 1, N / b如果NB(a)NB(b)不为空，即存在xNB(a)NB(b)，那么就一定有通路axb涂B颜色,满足题意。否则NB(a)NB(b)为空，假设性质Q成立： 任意任意x xNBNB( (a a)a a ，y yNBNB( (b b)b)b都有边都有边( (x x, , y y) )的颜色属于的颜色属于A A：那么显然任意一个点p，要么属于NA(a)，

39、要么属于NB(a)a。如果pNA(a)，就可以通过一次A颜色的边到达某个点aNB(a)a。同理任意一个点q，要么属于NA(b)，要么属于NB(b)b。如果qNA(b)，就可以通过一次A颜色的边到达某个点bNB(b)b。所以如果性质Q成立，任意两个点p和q，最长可以通过这样的路径pabq互相到达。这和“A不满足题意”的大前提不符。所以性质Q不成立，即至少存在一对(x, y)：xNB(a)a，yNB(b)a，有边(x, y)的颜色属于B。这样a和b就可以在颜色B诱导的子图中通过长度不大于3的路径互相到达了。定理成立。apqbyx有了这个定理，只需要任意找到两个有足够元素的集合A和B，输出一个满足条

40、件的即可。判断是否满足条件的过程可以采用Floyed，时间复杂度是O(N3) 1、将颜色序号小于等于（颜色数）div 2 的边权设为1(组成A集)；其它边权设4（组成B集）；、使用Floyed 算法计算任一顶点对间的最短路、若所有顶点对间的路长不超过3，则answer=1（A集满足条件）；否则answer= 2（B集满足条件） 、如果answer=1，则S中有颜色1（颜色数）div 2；否则S中有颜色（颜色数）div 2 颜色数计算计算S S集合中的颜色集合中的颜色 for i := 1 to N do将颜色序号小于等于（颜色数+1）div 2的边权标志为1；其它边权标志为4 for j :=

41、 1 to N do if datai , j = (C + 1) div 2 then datai , j := 1 else datai , j := 4; for k := 1 to N do计算任一顶点对间的最短路 for i := 1 to N do for j := 1 to N do if datai,k+datak,j= 4 then begin answer := 2; exit; end;输出输出S S集合中的颜色集合中的颜色 if answer = 1 若所有顶点对间的路长不超过3，则S中有颜色1（颜色数+1）div 2；否则S中有颜色（颜色数+1）div 2 +1颜色数

42、 then begin writeln(C + 1) div 2); for i := 1 to (C + 1) div 2 do write(i , ); writeln; end else begin writeln(C - (C + 1) div 2); for i := (C + 1) div 2 + 1 to C do write(i , ); writeln; end;如何计算图的最小点基，至少添多如何计算图的最小点基，至少添多少边才可使有向图变成强连通图少边才可使有向图变成强连通图基本思想计算所有强连通子图（传递闭包方法），并将强连通子图简化为顶点,保持各强连通子图之间的联系，使

43、问题得到简化。网络 一些学校连接在一个计算机网络上。学校之间存在软件支援协议。每个学校都有它应支援的学校名单（学校a支援学校，并不表示学校一定支援学校a）。当某校获得一个新软件时，无论是直接得到还是网络得到，该校都应立即将这个软件通过网络传送给它应支援的学校。因此，一个新软件若想让所有连接在网络上的学校都能使用，只需将其提供给一些学校即可。子任务子任务a a：请编一个程序，根据学校间支援协议（各个学校的支援名单），计算最少需要将一个新软件直接提供给多少个学校，才能使软件通过网络被传送到所有学校。子任务：子任务：如果允许在原有支援协议上添加新的支援关系。则总可以形成一个新的协议，使得此时只需将一

44、个新软件提供给任何一个学校，其他所有学校就都可以通过网络获得该软件。编程计算最少需要添加几条新的支援关系。输入数据：输入数据：文件inputtxt的第一行是一个正整数（），表示与网络连接的学校总数，随后行分别表示每个学校要支援的学校，即：i+1行表示第i号学校要支援的所有学校代号，最后结束。如果一个学校不支援任何其他学校，相应行则会有一个。一行中若有多个数字，数字之间以一个空格分隔。输出数据：输出数据：文件outputtxt，包含两行，第一行是一个正整数，表示子任务a的解，第二行也是一个正整数，表示子任务的解。将支援协议转换成有向图snet 学校作为结点，学校之间的支援关系作为有向边-若学校a

45、支援学校，则结点a向结点连一条有向边。 for i：=1 to n do begin 读学校i对口支援的学校j； while j0 do begin sneti，jtrue； 读学校i对口支援的学校j； end；while end；for子任务a求最小点基 直接获得软件的学校集合必须具备下述性质：对于任何一所学校vj，一定存在一所学校vi，使得vi是vj的前代。或者说中所有后代包含了有向图g的所有结点。这个集合就是所谓的点基。子任务a就是求一个包含结点数最小的点基。 最高的强连通分支和最低强连通分支极大强连通分支：极大强连通分支：有向图g至少能划分几个最大子图，使得每一个子图上的任一对结点可以

46、互相可达。这些子图称之为极大强连通分支。 最高的强连通分支和最低强连通分支：最高的强连通分支和最低强连通分支：设si、sj是有向图g的两个强连通分支。如果g中不存在终点属于si而起点不属于si的有向边，就称si为最高的强连通分支；如果g中不存在起点属于sj而终点不属于sj的有向边，就称sj为最低的强连通分支。 我们将有向图g的每个强连通分支紧缩成一个结点，保留各连通分支间相连的有效边，形成一个新的图g。g的所有结点中，入度为0的结点所代表强分支为最高强连通分支；出度为0的结点所代表强分支为最低强连通分支。求最小点基 如果结点集合b是一个点基，那么每个最高强连通分支si中至少有一个顶点要属于b。

47、最小点基b中的结点个数即为图g中最高强连通分支的个数，也是子任务a的解(直接获得软件的最少学校数)。图g的传递闭包snet(i ，j)=强分支间的传递闭包aneti,j=强分支的出入口标志序列。adegi,1强分支i的出口标志； adegi,2强分支i的入口标志； 无路至顶点顶点有路至顶点顶点jifalsejitrue;间无路至强分支强分支间有路至强分支强分支jifalsejitruefor k：=1 to n do for i：=1 to n do for j：=1 to n do sneti，jsneti，jor(sneti，kand snetk,j)；n10；fillchar(sblg，

48、 sizeof(sblg)，0)； 强分支序列初始化for i：=1 to n do if sblgi=0 then begin赋予结点i所在回路上的每一个结点一个强分支编号 n1n1+1； sblgin1； for j：=1 to n do if sneti，jand snetj，i then sblgjn1； end；thenfillchar(anet，sizeof(anet)，0)；强分支间的传递闭包初始化fillchar(adeg，sizeof(adeg)，0)； 强分支的出入口标志初始化for i：=1 to n do 计算强分支间的传递闭包 for j：=1 to n do if

49、(sblgisblgj) and (not anetsblgi，sblgj) then anetsblgi，sblgjsneti，j；for i：=1 to n1 do 依次搜索每一对分支 for j：=1 to n1 do if aneti，j若分支i至分支j有路，则置分支i出口标志，分支j入口标志 then begin adegi，1true； adegj，2true； end； then计算最小点基 依次搜索每一个强分支。若当前强分支的出口标志为false，则说明当前强分支是最低强连通分支；若当前强分支的入口标志为false，则说明当前强分支是最高强连通分支，最小点基的结点个数增1。计算

50、过程如下：设 r1最小点基的结点数； r2最小汇基的结点数； r10； r20； 点基的结点个数和汇基的结点个数初始化 for i：=1 to n1 do 顺序搜索每一个分支 begin if not adegi，1若第i个分支的出度为0，则说明分支为最低强分支，汇基的结点个数+1 then r2r2+1； if not adegi，2若第i个分支的入度为0，则说明分支为最高强分支，点基的结点个数+1 then r1r1+1； end； for 输出最小点基的结点数r1；子任务b求最小点基的结点数和最小汇基的结点数的最大值 如果图g是强连通图（n1=1），则在不用添加任何新的支援关系的情况下可

51、使所有学校共享软件资源，即任务b的解为0。如果图有多个强连通分支的话，就得计算图的点基和汇基。 所谓汇基指的是图g的一个结点子集p。每个最低强连通分支sj中至少有一个结点要属于p。最小汇基p中的结点个数即为图g的最低强连通分支的个数r2 。子任务b求最小点基的结点数和最小汇基的结点数的最大值 如果图g是强连通图（n1=1），则在不用添加任何新的支援关系的情况下可使所有学校共享软件资源，即任务b的解为0。如果图有多个强连通分支的话，就得计算图的点基和汇基。 所谓汇基指的是图g的一个结点子集p。每个最低强连通分支sj中至少有一个结点要属于p。最小汇基p中的结点个数即为图g的最低强连通分支的个数r2

52、 。若图g是非强连通图（n11）则添加的支援关系数为maxr1,r2，既先在点基和汇基间添加minr1,r2条有向边 ,然后添边连接剩余的maxr1,r2- minr1,r2个结点if n1=1 then 输出为0 else 输出添加的支援关系数为maxr1，r2；图的最小生成树图的最小生成树 对于一张图进行深度优先搜索或宽度优先搜索，可生成一棵深度优先搜索树或宽度优先搜索树。搜索的出发点不同，生成树的形态亦不同。在一张有权连通图中，如何寻找一棵各边权的总和为最小的生成树，就是本章节所要讨论的问题。 计算最小生成树的思维方向：计算最小生成树的思维方向：为了保证边权总和最小，必须保证、添加(u,

53、v)不能够形成回路、在保证的前提下添加权尽可能小的这样的边称之为安全边计算最小生成树的步骤：计算最小生成树的步骤：有两种算法可计算图的最小生成树 、KruskalKruskal算法算法 找出森林中连结任意两棵树的所有边中具有最小权值的边(u,v)作为安全边，并把它添加到正在生长的森林中。初始时，森林由单个结点组成的n棵树。 Kruskal算法算法 Const maxn=200; maxe=maxn*maxn;顶点数和边数的上限Type edgetype=Record边的类型 x,y,c:longint;边权为c的边（x，y） End;Var e:Array 1.maxe of edgetype

54、;边集，其中第i条边为(ei.x,ei.y)，该边的权为ei.c n,m,ans:longint;顶点数为n，边数为m f:Array 1.maxn of longint;并查集。其中fi为顶点i所在并查集的代表顶点，即子树根通过函数top(i)计算顶点i所在子树的根Function top(i:longint):longint;计算和返回顶点i所在并查集的代表顶点Beginif ifi Then fitop(fi);若i非所在并查集的代表顶点，则沿fi递归topfi;返回顶点i所在并查集的代表顶点End;top通过过程Union(i,j,c)合并顶点i和顶点j所在的两棵树现有边权为c的边（i

55、，j）。若该边的两个端点分属于两棵树，顶点i和顶点j所在子树的根分别为x和v，则(i,j) 加入最小生成树，合并两棵树（即顶点i和顶点j所在的并查集）。 Procedure Union(i,j,c:longint);合并i和j所在集合Var x,y:longint;Begin xtop(i); ytop(j);分别取出顶点i和顶点j所在子树的根if xy Then Begin inc(ans,c);fyx;End;若i和j分属于两棵子树，则该边权计入最小生成树的权和，两棵子树合并End; Union 主算法主算法按照边权值（c域值）递增的顺序排序边集e；For i1 to n Do fii;建

56、立由n棵树组成的森林，每棵树包含图的一个顶点ans0; 最小生成树的权和初始化为0For i1 to m Do Union(ei.x,ei.y,ei.c);枚举每条边，将两个端点分属两棵树的边加入最小生成树Writeln(ans);、PrimPrim算法算法集合A中的边总是只形成单棵树，每次添加到树中的边都是使树的权尽可能小的边。 设 di顶点i与生成树相连的最短边长； bai顶点i在生成树的标志； wi,j（i,j）的边长。若图中不存在边（i,j），则wi,j= min所有未在生成树的顶点的最小距离值fillchar(ba，sizeof(ba)，0)； 所有顶点未在生成树for i：=2 t

57、o n do di：=； 所有顶点的距离值初始化d1：=0 ；ans：=0；顶点1的距离值和生成树的权和初始化for i：=1 to n do begin 依次范围每个顶点 min：=oo；在所有未在生成树、且距离值最小（min）的顶点k for j：=1 to n do if not bajand(djmin) then begin k：=j；min：=dj；end；then if min=then begin ans：=-1；break；end；若这样的顶点不存在，则无解退出 ans：=ans+min；bak：=true；最小距离值min计入生成树的权和,顶点k进入生成树 for j：=1

58、 to n do调整与k相连的各顶点的距离值 begin min：=wk，j；if min0 then cp：=1 else cp：=-1；end；cpfunction dist(a，b：integer)：longint； 计算第a条机器蛇和第b条机器蛇间的距离，若ab之间有屏蔽，则距离设为无穷大 var i：integer；begin dist：=oo； for i：=1 to m do 如果a到b穿过第i个屏蔽，则返回无穷大 if (cp(w1i，w2i，sa)*cp(w1i，w2i，sb)=-1) and (cp(sa，sb，w1i)*cp(sa，sb，w2i)=-1) then exi

59、t； dist：=sqr(sa.x-sb.x)+sqr(sa.y-sb.y)；end； dist begin read(n)； 读入数据 for i：=1 to n do with si do read(x，y)； read(m)； for i：=1 to m do read(w1i.x，w1i.y，w2i.x，w2i.y)；用Prim算法求最小生成树 fillchar(ba，sizeof(ba)，0)； 所有机器蛇未访问 for i：=2 to n do di：=oo； 最短边长序列初始化 d1：=0 ；ans：=0； 从机器蛇1出发,通信网的最短长度初始化 for i：=1 to n do

60、 begin 访问n条机器蛇 min：=oo；在所有未访问的机器蛇中寻找与已访问的机器蛇相连且具有最短边长的机器蛇k for j：=1 to n do if not baj and (djmin) then begin k：=j； min：=dj；end；then if min=oo then begin ans：=-1； break； end；then若这样的机器蛇不存在，则无解退出 ans：=ans+sqrt(min)； bak：=true； 最短边长计入通信网,机器蛇k已访问 for j：=1 to n do 机器蛇k出发的所有不受屏蔽的边中，寻找边长最短的（k，j） begin min