信息学竞赛图论习题.doc

图论算法最小生成树算法(Prim算法)单源最短路径算法(Dijkstra算法)任意结点最短路径算法(Floyd算法)求有向带权图的所有环Bellman-Ford算法计算图的连通性计算最佳连通分支计算拓扑序列图论算法习题网络建设问题最短变换问题挖地雷乌托邦城市乌托邦交通中心某大学准备在校园网中构建校园网络，已知在校园网中选好了N（N1000）个点，并准备在这些点安装网络设备和电脑。若要将N个点互相连接起来，问怎样布线才能使得总距离最短，两点间的布线长度等于这两个点的几何距离。【输入】network.in输入文件的第一行为一个正整数N(1N100)。接下来N行，每行2个数U,V ，表示坐标。【输出】network.out输出最短路径距离（保留两位小数）【样例数据】 【输入】50 00 10 -11 0-1 0【输出】4.00 思路分析：此题可以应用PRIM算法解决，关键是根据输入文件算出图的邻接矩阵，然后可以直接应用PRIM算法。program network;const vmax=100;var w:array1.vmax,1.vmaxof real; x,y:array1.vmax of real; i,j,k,v,e:integer; sum:real;procedure prim(v0:integer); var flag:array1.vmax of boolean; min:real; prevk,nextk:integer; begin fillchar(flag,sizeof(flag),false); flagv0:=true; for i:=1 to v-1 do begin min:=1e38; for k:=1 to v do if flagk then for j:=1 to v do if (not flagj) and (wk,jmin) and (wk,j0) then begin min:=wk,j; nextk:=j; prevk:=k; end; if min1e10 then begin flagnextk:=true; writeln(prevk, ,nextk, ,min:0:2); 此部分输出每个结点对的距离，因题目不要求所以不输出。 sum:=sum+min; end; end; end;primbegin assign(input,network.in); reset(input); assign(output,network.out); rewrite(output); fillchar(w,sizeof(w),0); readln(v); for i:=1 to v do readln(xi,yi); for i:=1 to v do 计算图的邻接矩阵 begin for j:=i+1 to v do begin wi,j:=sqrt(sqr(xi-xj)+sqr(yi-yj); wj,i:=wi,j; end; end; sum:=0; prim(1); writeln(sum:0:2); close(input); close(output);end.无向图的生成树就是从图的边集中选择一些边，使得这些边构成一个连通无环图，也就是树。如果给每一条边加一个权，所有生成树中权和最小的生成树称为最小生成树。【Prim算法思想】任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。【最小生成树算法实例】 现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？【输入】 第一行两个数v(v=200),e，分别代表城市数和边数 以下e行，每行为两个顶点和它们之间的边权w(w1000)。【输出】 v-1行，每行为两个城市的序号，表明这两个城市间建一条公路，再加该公路的造价。 【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【输出样例】 1 2 10 2 3 5 2 4 6 2 6 11 4 5 18 原 图 最小生成树program prim_example;Const vmax=200var w:array1.vmax,1.vmaxof integer; i,j,k,v,e:integer;procedure prim(v0:integer); v0是开始结点 var flag:array1.vmax of boolean; min,prevk,nextk:integer; begin fillchar(flag,sizeof(flag),false); flagv0:=true; 先选出v0 for i:=1 to v-1 do 一共寻找v-1条边 begin min:=maxint; for k:=1 to v do if flagk then 找已在集合中的顶点 for j:=1 to v do 求满足条件的边的最小值 if (not(flagj) and (wk,jmin) and (wk,j0) then begin min:=wk,j; 记下最小值 nextk:=j; prevk:=k; end; if minmaxint then begin flagnextk:=true; 最小值对应顶点进入集合 writeln(prevk, ,nextk, ,min); end; end;for end;primbegin assign(input,prim.in); reset(input); assign(output,prim.out); rewrite(output); fillchar(w,sizeof(w),0); readln(v,e); for k:=1 to e do begin read(i,j); readln(wi,j); wj,i:=wi,j; end; prim(1); close(input); close(output);end.设图G=(V,E)是一个有向图,它的每一条边(U,V)都有一个非负权W(U,V)，在G中指定一个结点V0，要求从V0到G的每一个结点Vj的最短路径找出来（或指出不存在）。 由于源结点V0是给定的，所谓称为单源最短路径。【Dijkstra算法思想】 把所有结点分为两组。 第一组：包含已确定最短路径的结点。 第二组：包含尚未确定最短路径的结点。 按最短路径长度递增的顺序把第二组的结点加到第一组中去，直到V0可达的所有结点都包含于第一组中。在这个过程中，总保持从V0到第一组各结点的最短路径长度都不大于从V0到第二组任何结点的路径长度。 【单源最短路径算法实例】 现有一张县城的城镇地图，图中的顶点为城镇，无向边代表两个城镇间的连通关系，边上的权为公路造价，县城所在的城镇为v0。由于该县经济比较落后，因此公路建设只能从县城开始规划。规划的要求是所有可到达县城的城镇必须建设一条通往县城的汽车线路，该线路的工程总造价必须最少。【输入】 第一行一个整数v，代表城镇数，县城编号为1。 第二行是一个整数e，表示有向边数。 以下e行，每行为两个城镇编号和它们之间的公路造价。 【输出】 v-1行，每行为两个城市的序号，表明这两个城市间建一条公路。 【输入样例】 610 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【输出样例】 1 22 32 41 51 6 原 图从第1点出发的最短路径program dijkstra_example;const vmax=100;type path=record 此记录类型用于记录每一个结点与v0的距离和其父结点 length:integer; pre:0.vmax; end;var w:array1.vmax,1.vmax of integer; dist:array1.vmax of path; v,e,u,i,j,x,y:integer;procedure init; begin assign(input,dijkstra.in); reset(input); assign(output,dijkstra.out); rewrite(output); readln(v); readln(e); for i:=1 to v do for j:=1 to v do if ij then wi,j:=30000 30000只是一个较大的数的意思，实际应用于应该根据题目中给出的取值范围赋予一个充分大的数 else wi,j:=0; for i:=1 to e do begin read(x,y); readln(wx,y); wy,x:=wx,y; end; end;procedure dijkstra(v0:integer); var min:integer; begin wv0,v0:=1; v0首先进入第一组 for i:=1 to v do begin disti.length:=wv0,i; 计算每个结点的距离值 if disti.length30000 then disti.pre:=v0 如和v0直接有路，则置前驱结点为v0 else disti.pre:=0; end; repeat min:=30000; u:=0; for i:=1 to v do 找最短距离 if (wi,i=0) and (disti.lengthmin) then begin u:=i; min:=disti.length; end; if u0 then begin wu,u:=1; for i:=1 to v do 重新计算其他结点的距离值 if (wi,i=0) and (disti.lengthdistu.length+wu,i) then begin disti.length:=distu.length+wu,i; disti.pre:=u; end; end; until u=0;end;begin init; v0:=1; dijkstra(v0); for i:=1 to v do begin if (iv0) and (disti.length30000) then write(disti.pre, ,i); end; close(input); close(output);end.设图G=(V,E)是一个有向图,对于每对结点(U,V),找出从U到V的最短路径。【Floyd算法思想】 利用一个三重循环产生一个存储每个结点最短距离的矩阵.【Floyd算法实例】 现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表城市之间的距离。求每个城市的最短距离【输入】 第一行两个数v,e，分别代表城市数和边数 以下e行，每行为两个顶点和它们之间的边权。 【输出】 所有可能连接的城市的最短距离。 【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【输出样例】 1 2 101 3 151 4 161 5 191 6 212 3 52 4 62 5 242 6 113 4 63 5 243 6 164 5 184 6 145 6 32 program floyd_example;const maxn=10;var n,s,t,i,j:integer; dist:array1.maxn,1.maxn of real; prev:array1.maxn,1.maxn of 0.maxn;procedure init; var m,i,u,v:integer; begin assign(input,floyd.in); reset(input); assign(output,floyd.out); rewrite(output); readln(n,m); fillchar(prev,sizeof(prev),0); for u:=1 to n do for v:=1 to n do distu,v:=1e10; for i:=1 to m do begin readln(u,v,distu,v); distv,u:=distu,v; prevu,v:=u; prevv,u:=v; end; end;initprocedure floyd; var i,j,k:integer; begin for k:=1 to n do for i:=1 to n do for j:=1 to n do if (disti,k+distk,j,j); end; end;printbegin init; floyd; for i:=1 to n do for j:=i+1 to n do begin write(i, ,j, ); write(disti,j:0:0, ); print(i,j); writeln; end; close(input); close(output);end.求有向图的所有环,此问题包括了求最大环或者最小环。【输入】 第一行两个数v,e，分别代表图的顶点数和边数，以下e行，每行为有连接的两个顶点和权。 【输出】 顶点编号和环的长度以及包含该顶点的环的路径。 【输入样例】 huan.in5 71 2 22 1 12 5 43 2 53 4 74 1 35 4 6【输出样例】 huan.out1 3 1-22 3 2-14 15 4-1-2-55 15 5-4-1-2 program huan;const maxn=90;var n,s,t,i,j:integer; dist:array1.maxn,1.maxn of real; prev:array1.maxn,1.maxn of 0.maxn;procedure init; var m,i,u,v:integer; begin assign(input,huan.in); reset(input); assign(output,huan.out); rewrite(output); readln(n,m); fillchar(prev,sizeof(prev),0); for u:=1 to n do for v:=1 to n do distu,v:=1e10; for i:=1 to m do begin readln(u,v,distu,v); prevu,v:=u; end; end;procedure floyd;var i,j,k:integer;begin for k:=1 to n do for i:=1 to n do for j:=1 to n do if (disti,k+distk,j,j); end; end;printbegin init; floyd; for i:=1 to n do begin if disti,i1e10 then begin write(i, ); write(disti,i:0:0, ); print(i,previ,i); writeln; end; end; close(input); close(output);end.输入一张无向图，指出该图中哪些结点对之间有路。该问题通常采用传递闭包的计算方法。【输入】 n(顶点数，1n20) e(边数，1e210) 以下e行，每行为有边连接的一对顶点【输出】 k行，每行两个数，为存在通路的顶点对序号i,j(i5-6-4-2-3- program liantong_example;const maxv=20;var link,longlink:array1.maxv,1.maxv of boolean; f:array1.maxv of boolean; w:array1.maxv of integer; v,e,k,i,j,s,best,besti,max,maxk:integer;procedure init; begin assign(input,liantong.in); reset(input); assign(output,liantong.out); rewrite(output); fillchar(longlink,sizeof(longlink),0); fillchar(link,sizeof(link),0); readln(v); for i:=1 to v do readln(wi); readln(e); for k:=1 to e do begin readln(i,j); linki,j:=true; linkj,i:=true; end; end;initprocedure bibao; begin longlink:=link; for k:=1 to v do for i:=1 to v do for j:=1 to v do longlinki,j:=longlinki,j or (longlinki,k and longlinkk,j); end;bibaoprocedure dfs(i:integer); 深度优先搜索，用于输出路径 begin write(i,-); fi:=true; for j:=1 to v do if (not fj) and longlinki,j then dfs(j); end;dfsbeginmain init; bibao; for i:=1 to v do begin k:=0;s:=0; for j:=1 to v do 计算顶点i所在连通分支中的顶点总数和顶点的权和 if longlinki,j then begin k:=k+1; s:=s+wj; end; if kbest 求出顶点数的最大值 then begin best:=k; besti:=i; end; if smax 求出顶点权和的最大值 then begin max:=s; maxk:=i; end; if k=v then break; end; fillchar(f,sizeof(f),false); 结点是否访问数组初始化 dfs(besti); writeln; fillchar(f,sizeof(f),false); dfs(maxk); close(input); close(output);end.所谓拓扑序列，就是有向图的最长路径问题，如果图中存在环，则最长路径是无法求得的，所以有拓扑序列的有向图不可以存在环。具体定义如下： 给出有向图G=（V，E），若结点的线形序列V1,V2,.Vn满足条件：对于i,j(1jp2）。例如AB，BD，FD，对应的排队方案有三个：AFBD，FABD，ABFD【输入】 k行，每行a b，表示ab【输出】 一个可行的排队方案 【输入样例】 A BB DF D【输出样例】 ABFD program soldier_sort;var w:arrayA.Z,A.Z of 0.1; d:arrayA.Z of integer; 记录顶点入度的数组 s:set of A.Z; a,b,ch:char; m,n:string; i,j,k:integer;begin assign(input,tuopu.in); reset(input); assign(output,tuopu.out); rewrite(output); s:=; while not eof(input) do begin readln(a,ch,b); s:=s+a,b; 计算士兵名集合 wa,b:=1; db:=db+1; 累计顶点b的入度 end; m:=; for a:=A to Z do if a in s then m:=m+a; 产生士兵名字符集 k:=length(m); 求得士兵人数 n:=; 拓扑序列初始为空 for i:=1 to k do begin j:=1; while (dmj0) and (jk 若不存在入度为0的顶点，则无法拓扑排序失败 then begin writeln(Fault!); break; end; n:=n+mj; 入度为0的顶点进入拓扑序列n a:=mj; 删去顶点j da:=maxint; for j:=1 to k do 与a相连的顶点入度减1 if wa,mj0 then dmj:=dmj-1; end;for writeln(n); close(input); close(output);end.在一个地图上有n(n20)个地窖,每个地窖中埋有一定数量的地雷,给出地窖之间的联系路径。当地窖极其连接的数据给出之后,某人可以从任一处开始挖地雷,然后可以沿着指出的连接往下挖(仅能选择一条路径)，挖雷的过程中允许某人重复经过地窖。当无连接时，挖地雷工作结束。请编程设计一个挖地雷的方案，使某人能挖到的最多的地雷。 【输入文件】miner.in n(地窖个数)v1 v2 v3 . vn (每个地窖的地雷数)a(1,2) . a(1,n)a(2,3) . a(2,n).a(n-1,n) (表示地窖之间连接路径，其中a(i,j)表示地窖i,j之间是否有通路，若有通路，则a(i,j)=1，若无通路，则a(i,j)=0）【输出文件】miner.outR1-R2-.-Rk(挖地雷的顺序)Max(挖的地雷总数) 【样例数据】 【输入】miner.in62 10 20 8 5 70 0 0 1 11 0 0 00 0 00 11【输出】miner.out2-330利用计算最佳连通分支算法即可求得program miner;const maxv=20;var link,longlink:array1.maxv,1.maxv of boolean; a:array1.maxv,1.maxv of 0.1; f:array1.maxv of boolean; w:array1.maxv of integer; v,e,k,i,j,s,max,maxk:integer;procedure init; begin assign(input,miner.in); reset(input); assign(output,miner.out); rewrite(output); fillchar(longlink,sizeof(longlink),false); fillchar(link,sizeof(link),false); readln(v); for i:=1 to v do read(wi); readln; for i:=1 to v do begin for j:=i+1 to v do begin read(ai,j); if ai,j=1 then begin linki,j:=true; linkj,i:=true; end; end;for j readln; end;for i for i:=1 to v do begin for j:=1 to v do write(linki,j:6); writeln;end; end;initprocedure bibao; begin longlink:=link; for k:=1 to v do for i:=1 to v do for j:=1 to v do longlinki,j:=longlinki,j or (longlinki,k and longlinkk,j); end;bibaoprocedure dfs(i:integer); begin write(i, ); fi:=true; for j:=1 to v do if (not fj) and longlinki,j then dfs(j); end;dfsbeginmain init; bibao; max:=0; for i:=1 to v do begin s:=0; for j:=1 to v do if longlinki,j then s:=s+wj; if smax then begin max:=s; maxk:=i; end; end; fillchar(f,sizeof(f),false); dfs(maxk); writeln; write(max); close(input); close(output);end.住在乌托邦首都（编号为1）的天凯，开始对首都的交通情况感到不满，因为，他发现首都到某些城市，即使他选择最短的路径，距离也非常远。因此他想让你求一下交通中心城市是哪座城市（也有可能就是首都）。 为了说明交通中心城市的概念，先定义Gi为距离