#1769. [NOIP1996 提高组] 挖地雷

[NOIP1996 提高组] 挖地雷

当前没有测试数据。

题目描述

在一个地图上有NN个地窖(N20)(N \le 20),每个地窖中埋有一定数量的地雷。同时,给出地窖之间的连接路径。当地窖及其连接的数据给出之后,某人可以从任一处开始挖地雷,然后可以沿着指出的连接往下挖(仅能选择一条路径),当无连接时挖地雷工作结束。设计一个挖地雷的方案,使某人能挖到最多的地雷。

输入格式

有若干行。

11行只有一个数字,表示地窖的个数NN

22行有NN个数,分别表示每个地窖中的地雷个数。

33行至第N+1N+1行表示地窖之间的连接情况:

33行有n1n-1个数(0011),表示第一个地窖至第22个、第33个、…、第nn个地窖有否路径连接。如第33行为1100001 1 0 0 0 … 0,则表示第11个地窖至第22个地窖有路径,至第33个地窖有路径,至第44个地窖、第55个、…、第nn个地窖没有路径。

44行有n2n-2个数,表示第二个地窖至第33个、第44个、…、第nn个地窖有否路径连接。

… …

n+1n+1行有11个数,表示第n1n-1个地窖至第nn个地窖有否路径连接。(为00表示没有路径,为11表示有路径)。

输出格式

有两行

第一行表示挖得最多地雷时的挖地雷的顺序,各地窖序号间以一个空格分隔,不得有多余的空格。

第二行只有一个数,表示能挖到的最多地雷数。

样例 #1

样例输入 #1

5
10 8 4 7 6
1 1 1 0
0 0 0
1 1
1

样例输出 #1

1 3 4 5
27

提示

【题目来源】

NOIP 1996 提高组第三题