计算最佳连通分支.doc

在一张顶点带权的无向图中，计算含顶点数最多的一个连通分支和顶点权和最大的连通分支。【输入】 n(顶点数，1n20) 以下n行，其中第i行是顶点i的权 e(边数，1e210) 以下e行，每行为有边连接的一对顶点【输出】 含顶点数最多的一个连通分支 顶点权和最大的一个连通分支 【输入样例】 62102085751 51 62 34 65 6【输出样例】 1-5-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; fil