P2256.第2题-铺设消防栓

1000ms

Difficulty: 8

所属公司 : 华为

算法与标签>动态规划

题目内容

消防员正在给城市铺设消防栓，城市的道路可以看作一个连通且无回路的图，每条道路有两个底座，消防栓必须铺设在底座上，每条道路必须有消防栓盖；交叉路口只有一个消防栓底座；交叉路口的消防栓可以覆盖连接的所有道路，求至少需要多少个消防栓才能覆盖城市所有的道路?

每个 $case$ ，第一行一个整数 $n$ ，表示底座数。( $1<=n<=1500$ )

接下来 $n$ 行，每行以 $a:(b)$ 这样的格式开头， $a$ 表示底座的编号( $0<=a<=n-1$ ), $b$ 表示与该底座相连接的底座数，接下来 $b$ 个数，表示与该底座相连的底座编号。

一个数字，为需要的消防栓的最少个数

输入

3
0:(2) 1 2
1:(0)
2:(0)

输出

说明

$0$ 号底座与 $1$ 号和 $2$ 号相连，那么只需要在 $0$ 号铺设一个消防栓即可覆盖所有的道路，如下图所示：

输入

8
0:(3) 1 2 3
1:(1) 6
2:(0)
3:(0)
6:(1) 7
7:(2) 4 5
4:(0)
5:(0)

输出

说明

如图所示，在绿色节点上铺设消防栓即可覆盖全部道路

提示

动态规划

输入

预期输出（选填）