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

在一个地图上有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

LS的，奉劝一句，抄袭是不好的
还有，你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);
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.

2007全国信息学奥林匹克年鉴即将出版
　　
2007全国信息学奥林匹克年鉴
    ——信息学奥林匹克竞赛试题官方解题报告集锦

　　由中国计算机学会主编、NOI科学委员会主席王宏担任执行主编的一本全面反映2007年信息学奥林匹克竞赛的《2007全国信息学奥林匹克年鉴》现已出版。本书采用了书配盘的形式。
　　《2007全国信息学奥林匹克年鉴》完整地记录了2007年NOI和IOI相关的几次重大赛事活动；收录了NOIP、NOI、IOI、中国国家队选拔赛、冬令营的全部试题。在竞赛试题、 算法解析方面，本书中2007年NOI全部4次重要竞赛试题 的解题报告 均由命题者本人撰写完成，提供的命题背景与解题思路更加具体清晰，具有极高的权威性和参考价值。此外，本书配备的光盘，包含了命题者或选手的优秀程序和全套测试数据。
　　《2007全国信息学奥林匹克年鉴》是信息学奥赛选手和指导教师的重要参考资料，也是全国信息学奥林匹克的珍贵典藏。
    《2007全国信息学奥林匹克年鉴》2008年2月出版，定价40元/套（书＋光盘）。团购优惠，免邮资。
   
    邮购联系方式：
    地址：河南省郑州市经五路66号中小学电脑报社  邮编：450002   
    联系人： 田丽丽 
    电话： 0371-65333512 
    传真： 0371-65333505
    E-mail:  tllhpn8587@126.com

hehe 我也是

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

谢谢楼上的大牛！

忘点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.

错了错了，看下面一楼的我重发的
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.

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