信息学竞赛图论习题

5 6

program bibao_example; const

maxv=20; var

link,longlink:array[1..maxv,1..maxv] of boolean; v,e,k,i,j:integer; procedure init; begin

assign(input,'bibao.in'); reset(input);

assign(output,'bibao.out'); rewrite(output);

fillchar(longlink,sizeof(longlink),0); fillchar(link,sizeof(link),0); readln(v); readln(e);

for k:=1 to e do begin

readln(i,j);

link[i,j]:=true; {因为没有权，所以有布尔型表示连通关系，能提高运算速度}

link[j,i]:=true; end; end;{init} procedure bibao; begin

longlink:=link;

for k:=1 to v do {枚举中间顶点} for i:=1 to v do {枚举所有顶点对}

for j:=1 to v do {计算顶点i和顶点j的连通情况}

longlink[i,j]:=longlink[i,j] or (longlink[i,k] and longlink[k,j]); end;{bibao} procedure out; begin

for i:=1 to v-1 do for j:=i+1 to v do if longlink[i,j]

then writeln(i,' ',j); end;{out} begin{main} init; bibao; out;

13

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

在一张顶点带权的无向图中，计算含顶点数最多的一个连通分支和顶点权和最大的连通分支。 【输入】

n(顶点数，1≤n≤20)

以下n行，其中第i行是顶点i的权 e(边数，1≤e≤210)

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

含顶点数最多的一个连通分支 顶点权和最大的一个连通分支

【输入样例】 6 2 10 20 8 5 7 5 1 5 1 6 2 3 4 6 5 6

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

program liantong_example; const

maxv=20; var

link,longlink:array[1..maxv,1..maxv] of boolean; f:array[1..maxv] of boolean; w:array[1..maxv] of integer;

v,e,k,i,j,s,best,besti,max,maxk:integer; procedure init; begin

14

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(w[i]); readln(e);

for k:=1 to e do begin

readln(i,j); link[i,j]:=true; link[j,i]:=true; end; end;{init} procedure bibao; begin

longlink:=link; for k:=1 to v do for i:=1 to v do for j:=1 to v do

longlink[i,j]:=longlink[i,j] or (longlink[i,k] and longlink[k,j]); end;{bibao}

procedure dfs(i:integer); {深度优先搜索，用于输出路径} begin

write(i,'->'); f[i]:=true;

for j:=1 to v do

if (not f[j]) and longlink[i,j] then dfs(j); end;{dfs} begin{main} init; bibao;

for i:=1 to v do begin

k:=0;s:=0;

for j:=1 to v do {计算顶点i所在连通分支中的顶点总数和顶点的权和} if longlink[i,j] then begin k:=k+1; s:=s+w[j];

15

end;

if k>best {求出顶点数的最大值} then begin

best:=k; besti:=i; end;

if s>max {求出顶点权和的最大值} 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(1≤j

【拓扑排序主要思想】

有向图可以拓扑排序的条件是：图中没有环。 具体方法：

⑴ 从图中选择一个入度为0的点加入拓扑序列。

⑵ 从图中删除该结点以及它的所有出边（即与之相邻点入度减1）。 反复执行这两个步骤，直到所有结点都已经进入拓扑序列。

【实例：士兵排队问题】

有n个士兵(1≤n≤26)，依次编号为A,B,C,...，队列训练时，指挥官要把一些士兵从高到矮排成一行。但现在指挥官不能直接获得每个人的身高信息，只能获得“p1比p2高”这样的比较结果，记作（p1>p2）。例如A>B，B>D，F>D，对应的排队方案有三个：AFBD，FABD，ABFD 【输入】

k行，每行a b，表示a>b 【输出】

一个可行的排队方案

16