求救：挖地雷！ [复制链接]

在一个地图上有N个地窖（N<=20），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。
例如：
[题目要求]
当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。
输入格式： N： （表示地窖的个数）
Ｗ1，W2，W3，……WN （表示每个地窖中埋藏的地雷数量）
A12…………… . A1N (aij=1表示第i个地窖与第j个地窖有连接，=0表示无连接)
A23…………..A2N
……..
AN-1 N
输出格式：K1--K2--……….KV （挖地雷的顺序）
MAX （挖地雷的数量）

其输入格式为：
5
10 8 4 7 6
1 1 1 0
0 0 0
1 1
1
输出：1 -3 -4 -5
max=27

大家帮帮忙啊！

动规嘛．．．．．．．．．．．．．．．

hui

我要的是具体思路和解法！！

错了错了，看下面一楼的我重发的
var
i,j,n:integer;
a,pre,count:array[1..20] of integer;
con:array[1..20,1..20] of integer;
first:boolean;

procedure print(a:integer);
begin
  if pre[a]<>0
  then
    print(pre[a]);
  if first
  then first:=false
  else write('-');
  write(a);
end;

begin
read(n);
for i:=1 to n do
  read(a);
for i:=1 to n-1 do
  for j:=i+1 to n do
  read(con[i,j]);
for i:=1 to n do
  begin
  count:=a;
  pre:=0;
  end;

for i:=2 to n do
  for j:=1 to i-1 do
  if (count[j]+a>count) and (con[j,i]=1)
    then
    begin
      count:=count[j]+a;
      pre:=j;
    end;
j:=1;
for i:=1 to n do
  if count>count[j]
  then
    j:=i;
first:=true;
print(j);
writeln;
write('max=',count[j]);
end.

忘点WIND CODE了
重发一遍
var
i,j,n:integer;
a,pre,count:array[1..20] of integer;
con:array[1..20,1..20] of integer;
first:boolean;

procedure print(a:integer);
begin
  if pre[a]<>0
  then
    print(pre[a]);
  if first
  then first:=false
  else write('-');
  write(a);
end;

begin
read(n);
for i:=1 to n do
  read(a[i]);
for i:=1 to n-1 do
  for j:=i+1 to n do
  read(con[i,j]);
for i:=1 to n do
  begin
  count[i]:=a[i];
  pre[i]:=0;
  end;

for i:=2 to n do
  for j:=1 to i-1 do
  if (count[j]+a[i]>count[i]) and (con[j,i]=1)
    then
    begin
      count[i]:=count[j]+a[i];
      pre[i]:=j;
    end;
j:=1;
for i:=1 to n do
  if count[i]>count[j]
  then
    j:=i;
first:=true;
print(j);
writeln;
write('max=',count[j]);
end.

谢谢楼上的大牛！

大牛？不敢当
这道题是JSOI2007夏令营B层次的动态规划的例题，去年我初一去参加的，正好记在笔记上

hehe 我也是