A91470.最少学习费用
普及/提高-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
“BerCorp” 公司有 n 名员工。这些员工可以使用 m 种被批准的官方语言进行正式交流。
语言用整数 1∼m 编号。
对于每一位员工,我们知道 TA 当前会的语言列表,这个列表可能为空(即有的员工现在不会任何官方语言)。
不过好消息是:员工们都愿意学习新的语言,只要公司替他们付学费。每名员工学习一门语言的费用为 1 伯币,同一个人可以学多门语言,费用按门数累加。
如果两位员工会的语言中有至少一门是相同的,就认为他们可以直接交流。
如果员工 A 可以和员工 B 交流,员工 B 可以和员工 C 交流,那么也认为 A 可以通过 B 间接和 C 交流。
现在,公司想花尽量少的钱,让任意一位员工都能(直接或间接)与任何其他员工进行交流。
请你计算公司至少需要花费多少伯币。
输入格式
第一行包含两个整数 n 和 m(2≤n,m≤100),分别表示员工人数和官方语言的数量。
接下来 n 行,第 i 行描述第 i 位员工现在会的语言:
- 这一行的第一个整数为 ki(0≤ki≤m),表示第 i 位员工会的语言个数;
- 接下来有 ki 个整数 ai1,ai2,…,aiki(1≤aij≤m),表示这些语言的编号。
保证同一名员工的语言列表中不会出现重复的语言编号。
注意,可能存在 ki=0 的员工(即目前不会任何官方语言)。
同一行中相邻两个整数之间用一个空格隔开。
输出格式
输出一个整数,表示为了让任意两名员工都可以(直接或间接)交流所需要花费的最少总费用。
输入输出样例
输入#1
5 5 1 2 2 2 3 2 3 4 2 4 5 1 5
输出#1
0
输入#2
8 7 0 3 1 2 3 1 1 2 5 4 2 6 7 1 3 2 7 4 1 1
输出#2
2
输入#3
2 2 1 2 0
输出#3
1
说明/提示
样例解释 #1
五名员工会的语言分别为:
- 员工 1:{2}
- 员工 2:{2,3}
- 员工 3:{3,4}
- 员工 4:{4,5}
- 员工 5:{5}
可以发现,他们通过这些语言本身就已经“串成了一条链”,任意两人之间都可以通过若干中间人间接交流,因此不需要再额外学习语言,答案为 0。
样例解释 #2
- 员工 1:不会任何语言;
- 员工 2:{1,2,3};
- 员工 3:{1};
- 员工 4:{5,4};
- 员工 5:{6,7};
- 员工 6:{3};
- 员工 7:{7,4};
- 员工 8:{1}。
一种可行的最优方案是:
- 让员工 1 学习语言 2;
- 让员工 8 学习语言 4。
此时所有员工都会被连成一个整体,花费为 2,可以证明这是最小值。
样例解释 #3
- 员工 1:{2};
- 员工 2:不会任何语言。
只要让员工 2 学习语言 2,两人就可以直接交流,花费为 1。显然这是最优方案。