noip pascal图论.doc

1.输入一张无向图，指出该图中哪些结点对之间有路。(pass!)【输入】 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 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);end.设图G=(V,E)是一个有向图,对于每对结点(U,V),找出从U到V的最短路径。【Floyd算法思想】 利用一个三重循环产生一个存储每个结点最短距离的矩阵.【Floyd算法实例】 3.现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表城市之间的距离。求每个城市的最短距离【输入】 第一行两个数v,e，分别代表城市数和边数 以下e行，每行为两个顶点和它们之间的边权。 【输出】 所有可能连接的城市的最短距离。(pass了，但不知道fillchar怎么初始最大化) 【输入样例】 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.4.求有向图的所有环,此问题包括了求最大环或者最小环。【输入】 第一行两个数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.第一章 最小生成树1.1 实际背景与算法1.2 例题与习题5.1 实际背景与算法实际背景:要在n个居民点之间架设煤气管道,很显然最多可架设 n(n-1)/2条管道,然而要连通n个居民点架设n-1条管道(无环出现)就可以了,为了使造价最小,选择哪n-1条边?这就是最小生成树问题。算法1（prim算法）：1）图采用邻接矩阵存储。2）找到目前情况下能连上的权值最小的边的另一端点，加入之，直到所有的顶点加入完毕。算法2（kruskal算法）：1）图采用边目录方式存储。2）选目前情况下能连上的权值最小的边，若与以生成的树不够成环，加入之，直到n-1条边加入完毕。5.2例题与习题1：求下图的最小生成树程序1（使用算法1）如下：program mintree;const maxn=100;var cost:array1.maxn,1.maxn of integer; lowcost,closet:array1.maxn of integer; n,mincost:integer;procedure init;var i,j:integer;beginreadln(n);for i:=1 to n do for j:=1 to n do read(costi,j);for i:=1 to n do begin lowcosti:=cost1,i; closeti:=1 end ;mincost:=0;end;procedure prim;var i,j,k,min:integer;beginfor i:=1 to n-1 do begin min:=32767; for j:=1 to n do if (lowcostj0) and (lowcostjmin) then begin min:=lowcostj;k:=j; end; mincost:=mincost+costclosetk,k; writeln(,closetk,k,); lowcostk:=0; for j:=1 to n do if costk,jlowcostj then begin lowcostj:=costk,j;closetj:=k end;end;end;begininit;prim;writeln(treeminlength=,mincost);readln;end.程序2（使用算法2）如下：program shchtree;var n,m,i,j:integer;selected:array1.100 of integer;e:array1.100,1.2 of integer;value:array1.100 of integer;t:array1.100 of integer;min,mine,valuet:integer;beginwrite(Input n and m:);read(n,m);writeln(input data:);for i:=1 to m do readln(ei,1,ei,2,valuei);fillchar(selected,sizeof(selected),0);fillchar(t,sizeof(t),0);valuet:=0;for i:=1 to n-1 do begin min:=maxint; mine:=0; for j:=1 to m do if selectedj=0 then if (tej,1=0) xor (tej,2=0) or (i=1) then if valuejmin then begin min:=valuej;mine:=j; end; selectedmine:=1; temine,1:=1; temine,2:=1; valuet:=valuet+min; end; for i:=1 to m do if selectedi=1 then begin writeln(,ei,1,ei,2,); end;writeln(tree: ,length=,valuet);readln;end.6.无向图的生成树就是从图的边集中选择一些边，使得这些边构成一个连通无环图，也就是树。如果给每一条边加一个权，所有生成树中权和最小的生成树称为最小生成树。【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.第二章 最短路径2.1 单对顶点间的最短路径2.2 一点到其它所有点的最短路径2.3 所有点间的最短路径2.1 单对顶点间的最短路径 例1：输入起点，终点，求其最短路径？ 1.下面是Dijkstra 算法： 基本思想是：设置一个顶点的集合s，并不断地扩充这个集合，一个顶点属于集合s当且仅当从源点到该点的路径已求出。开始时s中仅有源点，并且调整非s中点的最短路径长度，找当前最短路径点，将其加入到集合s，直到终点在s中。 program zudlouj;const n=6;max=10000 ; cost:array1.6,1.6 of real=(0,50,10,max,45,max),(max,0 ,15,max,10,max),(20,max,0,15,max,max),(max,20,max,0,35,max),( max,max,max,30,0,max),(max,max,max,3,max,0);var dist:array1.n of real; path,p:array1.n of 1.n; first,tail,u:1.n; s:set of 1.n; i,j,y,m:integer; min:real;beginread(first,tail);for i:=1 to n do disti:=max;distfirst:=0;s:=first; u:=first;while utail do begin for j:= 1 to n do if not(j in s) and (distu+costu,jdistj) then begin distj:=distu+costu,j;pathj:=u end; min:=max; for j:=1 to n do if not(j in s) and (distjmin) then begin u:=j;min:=distj;end; if min=max then begin writeln(No answer);halt end; s:=s+u; end; writeln(mindist(,first,tail,)=,disttail:8:2); y:=tail;m:=0; while (yfirst) do begin inc(m);pm:=y;y:=pathy; end; write(path:,first); for j:=m downto 1 do write(-,pj); writeln;end. 2.迭代算法(ford算法) Dijkstra 算法只能适合权为正值的情况,但当权为负值时，是Dijkstra 算法爱莫能助，这时只要图中不存在负权回路可用迭代算法。 迭代算法的思想：不停地调整图中的顶点值（源点到该点的最短路径值），直到没有点的值调整了为止。 程序如下： program zudlouj;const n=6;max=10000 ; cost:array1.6,1.6 of real=(0,50,10,max,45,max),(max,0 ,15,max,10,max),(20,max,0,15,max,max),(max,20,max,0,35,max),( max,max,max,30,0,max),(max,max,max,3,max,0);var dist:array1.n of real; path,p:array1.n of 1.n; first,tail,u:1.n; s:set of 1.n; i,j,y,m:integer; min:real; quit:boolean;beginread(first,tail);for i:=1 to n do disti:=max;distfirst:=0; repeat quit:=true; for i:=1 to n do if distimax then for j:=1 to n do if disti+costi,jdistj then begin distj:=disti+costi,j; pathj:=i; quit:=false; end; until quit; writeln(mindist(,first,tail,)=,disttail:8:2); y:=tail;m:=0; while (yfirst) do begin inc(m);pm:=y;y:=pathy; end; write(path:,first); for j:=m downto 1 do write(-,pj); writeln;end. 2. 2 一点到其它所有点的最短路径 例2：如下图：求起点到所有点的最短路径？ 1.下面是Dijkstra 算法： 基本思想是：设置一个顶点的集合s，并不断地扩充这个集合，一个顶点属于集合s当且仅当从源点到该点的路径已求出。开始时s中仅有源点，并且调整非s中点的最短路径长度，找当前最短路径点，将其加入到集合s中，直到所有的点都在s中。 program zudlouj;const n=6;max=10000 ; cost:array1.6,1.6 of real=(0,50,10,max,45,max),(max,0 ,15,max,10,max),(20,max,0,15,max,max),(max,20,max,0,35,max),( max,max,max,30,0,max),(max,max,max,3,max,0);var dist:array1.n of real; path,p:array1.n of 1.n; first,u:1.n; s:set of 1.n; i,j,y,m:integer; min:real;beginread(first);for i:=1 to n do disti:=max;distfirst:=0;s:=first; u:=first;for i:=1 to n-1 do begin for j:= 1 to n do if not(j in s) and (distu+costu,jdistj) then begin distj:=distu+costu,j;pathj:=u end; min:=max; for j:=1 to n do if not(j in s) and (distjmin) then begin u:=j;min:=distj;end; s:=s+u; end;for i:=1 to n do if ifirst then if distimax then begin writeln(mindist(,first,i,)=,disti:8:2); y:=i;m:=0; while (yfirst) do begin inc(m);pm:=y;y:=pathy end; write(path:,first); for j:=m downto 1 do write(-,pj); writeln; end else writeln(mindist(,first,i,):,No answer);end. 2.ford算法 program zudlouj;const n=6;max=10000 ; cost:array1.6,1.6 of real=(0,50,10,max,45,max),(max,0 ,15,max,10,max),(20,max,0,15,max,max),(max,20,max,0,35,max),( max,max,max,30,0,max),(max,max,max,3,max,0);var dist:array1.n of real; path,p:array1.n of 1.n; first,tail,u:1.n; s:set of 1.n; i,j,y,m:integer; min:real; quit:boolean;beginread(first);for i:=1 to n do disti:=max;distfirst:=0; repeat quit:=true; for i:=1 to n do if distimax then for j:=1 to n do if disti+costi,jdistj then begin distj:=disti+costi,j; pathj:=i; quit:=false; end; until quit; for i:=1 to n do if ifirst then if distimax then begin writeln(mindist(,first,i,)=,disti:8:2); y:=i;m:=0; while (yfirst) do begin inc(m);pm:=y;y:=pathy end; write(path:,first); for j:=m downto 1 do write(-,pj); writeln; end else writeln(mindist(,first,i,):,No answer); end. 2.所有点间的最短路径弗洛耶德算法（Floyed算法）： 基本思想：求解所有点间的路径需要进行n次试探。对于顶点i到顶点j的路径长度，首先考虑让路径经过顶点1，比较路径（i，j）和（i，1，j）的长度取其短者为当前求得的最短路径长度。对每一对顶点的路径都做这样的试探，则可求得一个矩阵设为A(1)，求n次即得每对顶点间的最短路径A(n)。A(0)=A：邻接矩阵。如下图： A(0)-A(4) 0411041104850485046510041100411004190417021505905901059010590101010106101061010P(0)-P(4)00000000002200220042000000000000300030000000010001020102010200000000000033003300程序如下：program floyed;const n=4;varcost,a:array1.n,1.nof integer;p:array1.n,1.n of 0.n;i,j,k:integer;procedure init;var i,j:integer;beginfor i:=1 to n do for j:=1 to n do begin read(costi,j); ai,j:=costi,j; pi,j:=0; end;end;procedure path(i,j:integer);var k:integer;begink:=pi,j;if k0 then begin path(i,k);write(-,k);path(k,j);endend;begininit;for k:=1 to n do for i:=1 to n do for j:=1 to n do if ai,k+ak,jai,j then begin ai,j:=ai,k+ak,j; pi,j:=k; end;for i:=1 to n do for j:=1 to n do if ij then begin writeln(a,i,j,=,ai,j); write(i); path(i,j); writeln(-,j) end;end.注意：弗洛耶德算法（Floyed算法）思想可用与判断有向图中任意两点是否连通？算法如下： for k:=1 to n do for i:=1 to n do for j:=1 to n do if （ai,k=1）and (ak,j=1) then ai,j=1 (ai,j=1表示i可达j，ai,j=0表示i不可达j）。设图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行，每行为两个城市的序号，表明这两个城市间建一条公路。 【输入样例】 6