P2196 [NOIP 1996 Senior] Digging Mines

On a map there are $N$ ($N \le 20$) cellars, each containing a certain number of mines. The connections between cellars are given. After the data of the cellars and their connections are provided, a person can start digging mines from any cellar. Each time, they may move to a connected cellar whose index is strictly larger than the current node’s index to dig mines. The digging ends when there is no node that satisfies the condition. Design a digging plan so that the person can collect the maximum number of mines.

Multiple lines. The first line contains a single integer, the number of cellars $N$. The second line contains $N$ integers, representing the number of mines in each cellar. Lines $3$ to $N+1$ describe the connections between cellars: - Line $3$ has $N-1$ numbers ($0$ or $1$), indicating whether there is a path from the first cellar to the $2$-nd, $3$-rd, …, $N$-th cellar. For example, if line $3$ is $1\ 1\ 0\ 0\ 0 \cdots 0$, it means there is a path from cellar $1$ to cellar $2$, a path from cellar $1$ to cellar $3$, and no path from cellar $1$ to cellar $4$, cellar $5$, …, cellar $N$. - Line $4$ has $N-2$ numbers, indicating whether there is a path from the second cellar to the $3$-rd, $4$-th, …, $N$-th cellar. - … - Line $N+1$ has $1$ number, indicating whether there is a path from the $(N-1)$-th cellar to the $N$-th cellar (where $0$ means no path and $1$ means there is a path).

The first line prints the digging order when the maximum number of mines is collected. The indices of the cellars are separated by a single space, with no extra spaces. The second line contains a single integer, the maximum number of mines that can be collected.

[Sample Explanation]  The optimal path is $1 \to 3 \to 4 \to 5$, and the result is $27$. [Source] NOIP 1996 Senior, Problem 3. Translated by ChatGPT 5