信息学竞赛图论习题

dist:array[1..maxn,1..maxn] of real; prev:array[1..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 dist[u,v]:=1e10; for i:=1 to m do begin

readln(u,v,dist[u,v]); dist[v,u]:=dist[u,v]; prev[u,v]:=u; prev[v,u]:=v; end; end;{init} 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 (dist[i,k]+dist[k,j]

dist[i,j]:=dist[i,k]+dist[k,j]; prev[i,j]:=prev[k,j]; end; end;{floyd}

procedure print(i,j:integer); begin if i=j

then write(i)

else if prev[i,j]=0

then write('No Solution!') else begin

print(i,prev[i,j]);

9

write('->',j); end; end;{print} begin init; floyd;

for i:=1 to n do for j:=i+1 to n do begin

write(i,' ',j,' ');

write(dist[i,j]:0:0,' '); print(i,j); writeln; end;

close(input); close(output); end.

求有向图的所有环,此问题包括了求最大环或者最小环。 【输入】

第一行两个数v,e，分别代表图的顶点数和边数，以下e行，每行为有连接的两个顶点和权。 【输出】

顶点编号和环的长度以及包含该顶点的环的路径。

【输入样例】 huan.in 5 7 1 2 2 2 1 1 2 5 4 3 2 5 3 4 7 4 1 3 5 4 6

【输出样例】 huan.out 1 3 1->2 2 3 2->1

4 15 4->1->2->5 5 15 5->4->1->2

program huan; const

maxn=90;

10

var

n,s,t,i,j:integer;

dist:array[1..maxn,1..maxn] of real; prev:array[1..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 dist[u,v]:=1e10; for i:=1 to m do begin

readln(u,v,dist[u,v]); prev[u,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 (dist[i,k]+dist[k,j]

dist[i,j]:=dist[i,k]+dist[k,j]; prev[i,j]:=prev[k,j]; end; end;{floyd}

procedure print(i,j:integer); begin if i=j

then write(i)

else if prev[i,j]=0

then write('No Circle!') else begin

print(i,prev[i,j]);

11

write('->',j); end; end;{print} begin init; floyd;

for i:=1 to n do begin

if dist[i,i]<>1e10 then begin

write(i,' ');

write(dist[i,i]:0:0,' '); print(i,prev[i,i]); writeln; end; end;

close(input); close(output); end.

输入一张无向图，指出该图中哪些结点对之间有路。该问题通常采用传递闭包的计算方法。 【输入】

n(顶点数，1≤n≤20) e(边数，1≤e≤210)

以下e行，每行为有边连接的一对顶点 【输出】

k行，每行两个数，为存在通路的顶点对序号i,j(i

【输入样例】 6 5 1 5 1 6 2 3 4 6 5 6

【输出样例】 1 4 1 5 1 6 2 3 4 5 4 6

12