第8讲：图的基本概念和算法.ppt

邻接矩阵：代码书写简单，找邻接点慢 邻接表：代码书写较复杂，找邻接点快 稀疏图：边表 type node=record w:integer; //边权 u,v:integer; //两个结点 end; var e: array[1..maxn*(maxn-1) div 2] of node; //边 求无向的连通分量 sum:=0; for i:=1 to n do if not f[i] then begin inc(sum); dfs(i); end; writeln(sum); //noip2001 const maxn=51; var a:array[0..9,0..9] of boolean; f:array[0..9] of integer; ans:array[0..500] of shortint; s:string; n,len:integer; 构图 procedure init; var k,i,p,q:integer; begin fillchar(a,sizeof(a),false); for i:=0 to 9 do a[i,i]:=true; readln(s); readln(k); for i:=1 to k do begin readln(p,q); a[p,q]:=true; end; end; 生产数组f procedure makef; var i,j,k:integer; begin for k:=0 to 9 do for i:=0 to 9 do for j:=0 to 9 do a[i,j]:=a[i,j]or(a[i,k] and a[k,j]); for i:=0 to 9 do for j:=0 to 9 do if a[i,j] then inc(f[i]); end; procedure mul(k:integer); //高精度乘单精度 var i,m:integer; begin len:=ans[0]; for i:=1 to len do ans[i]:=ans[i]*k; for i:=1 to len do begin ans[i+1]:=ans[i+1]+ans[i] div 10; ans[i]:=ans[i] mod 10; end; m:=ans[len+1]; while m0 do begin inc(len); ans[len]:=m mod 10; m:=m div 10; end; ans[0]:=len; end; main procedure main; var i,k:integer; begin makef; n:=length(s); fillchar(ans,sizeof(ans),0); ans[1]:=1; ans[0]:=1; for i:=1 to n do begin k:=f[ord(s[i])-48]; if k0 then mul(k); end; end; procedure print; var i:integer; begin for i:=ans[0] downto 1 do write(ans[i]); writeln; end; begin init; main; print; end. 分析： 求出任意两点间的最短距离。 枚举每一个顶点到其他n-1个点的最短距离和。 最小者即所求目标。 由邻接矩阵a先求出f[i,j] for i:=1 to n do for j:=1 to n do if a[i,j]maxint then