P2196 [NOIP 1996 提高组] 挖地雷

题目描述

在一个地图上有 $N\ (N \le 20)$ 个地窖,每个地窖中埋有一定数量的地雷。同时,给出地窖之间的连接路径。当地窖及其连接的数据给出之后,某人可以从任一处开始挖地雷,然后每次可以移动到一个编号比当前节点大且联通的节点去挖地雷,当无满足条件的节点时挖地雷工作结束。设计一个挖地雷的方案,使某人能挖到最多的地雷。

输入格式

输出格式

说明/提示

**【样例解释】** ![](https://img.picui.cn/free/2025/05/15/6825a221c60ba.png) 最优路径为 $1 \to 3 \to 4 \to 5$,结果为 $27$。 **【题目来源】** NOIP 1996 提高组第三题。