在一个地图上有n(n≤20)个地窖,每个地窖中埋有一定数量的地雷,给出地窖之间的联系路径。当地窖极其连接的数据给出之后,某人可以从任一处开始挖地雷,然后可以沿着指出的连接往下挖(仅能选择一条路径)，挖雷的过程中允许某人重复经过地窖。当无连接时，挖地雷工作结束。请编程设计一个挖地雷的方案，使某人能挖到的最多的地雷。 【输入文件】miner.in n(地窖个数)v1 v2 v3 … vn (每个地窖的地雷数)a(1,2) … a(1,n)a(2,3) … a(2,n) . . .a(n-1,n) (表示地窖之间连接路径，其中a(i,j)表示地窖i,j之间是否有通路，若有通路，则a(i,j)=1，若无通路，则a(i,j)=0）【输出文件】miner.outR1-R2-…-Rk(挖地雷的顺序)Max(挖的地雷总数)【样例数据】 【输入】miner.in62 10 20 8 5 70 0 0 1 11 0 0 00 0 00 11 【输出】miner.out2-330
{利用计算最佳连通分支算法即可求得}
program miner;
const
maxv=20;
var
link,longlink:array[1..maxv,1..maxv] of boolean;
a:array[1..maxv,1..maxv] of 0..1;
f:array[1..maxv] of boolean;
w:array[1..maxv] of integer;
v,e,k,i,j,s,max,maxk:integer;
procedure init;
begin
assign(input,'miner.in');
reset(input);
assign(output,'miner.out');
rewrite(output);
fillchar(longlink,sizeof(longlink),false);
fillchar(link,sizeof(link),false);
readln(v);
for i:=1 to v do
read(w[i]);
readln;
for i:=1 to v do
begin
for j:=i+1 to v do
begin
read(a[i,j]);
if a[i,j]=1
then begin
link[i,j]:=true;
link[j,i]:=true;
end;
end;{for j}
readln;
end;{for i}
for i:=1 to v do begin
for j:=1 to v do
write(link[i,j]:6);
writeln;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;
max:=0;
for i:=1 to v do
begin
s:=0;
for j:=1 to v do
if longlink[i,j]
then s:=s+w[j];
if s>max
then begin
max:=s;
maxk:=i;
end;
end;
fillchar(f,sizeof(f),false);
dfs(maxk);
writeln;
write(max);
close(input);
close(output);
end.
开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明Pascal经典算法 – 挖地雷！
