挖地雷

题目描述:

有n个地牢，第i个地牢有wi个地雷，有的地牢之间有边，有的则无边（注意，边是单向的！），问，一个人从任意一个地牢出发，每经过一个地牢都可以把地雷挖出来，直到不能再走为止。问，这个人最多能挖多少个地雷？

输入格式:

第一行一个n，意义同题目。

第二行有n个数，用空格隔开，第i个数表示wi，意义同题目。

接下来n-1行，这里面第i行有n-i个数，若第i行第j列为1表示从地牢i到地牢j有道路联通。注意，若地牢i到地牢j有路径，那么地牢j到地牢i就保证没有路径。

输出格式:

第一行输出一个数maxx，表示最大可挖出多少。

样例输入:

5
10 20 5 4 5
1 1 0 1
0 0 1
0 0
0

样例输出:

35

提示:

对于100%的数据：n<=200，最终结果小于等于10000。

时间限制: 1000ms
空间限制: 256MB

---

来源: by zhr