社区讨论

求助

学术版参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo2ayjpp
此快照首次捕获于
2023/10/23 10:52
2 年前
此快照最后确认于
2023/11/03 11:03
2 年前
查看原帖

题目描述

小明一家在一个巨大的城堡里,古堡里有N 个房间,有些房间之间有过道相连,城堡里一共有N-1 条道,通过这些过道,小明可以从任一间房间走到另外一间房间。由于城堡建在山上,所以小明需要考虑安全防护问题,G 公司现在有一款安全产品,只要在一个房间里面安装,就可以监控和这房间连接的所有过道,但是这人产品非常贵,所以小明要节约一点使用。他想知道,至少要安装多少套产品,就可以把所有的过道都监控起来。

输入

第一行一个整数 N,表示房间的数量 第二行到第 N+1行,每行描述一个房间的信息,依次为:该房间的编号,相接的过道数量k,接下来k个整数,分别是
r1,r2,,rkr_{1},r_{2},\cdots,r_{k}
每条过道的另一个房间的编号对于每一条过道,在输入中只会出现一次、也就是说,对于连接两房间的过道,要么在x房间的信息中出现,要么在y房间的信息中出现

输出

一个整数,表示至少需要安装安全产品的套数

回复

4 条回复,欢迎继续交流。

正在加载回复...