A91470.最少学习费用

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

“BerCorp” 公司有 nn 名员工。这些员工可以使用 mm 种被批准的官方语言进行正式交流。
语言用整数 1m1 \sim m 编号。

对于每一位员工,我们知道 TA 当前会的语言列表,这个列表可能为空(即有的员工现在不会任何官方语言)。
不过好消息是:员工们都愿意学习新的语言,只要公司替他们付学费。每名员工学习一门语言的费用为 11 伯币,同一个人可以学多门语言,费用按门数累加。

如果两位员工会的语言中有至少一门是相同的,就认为他们可以直接交流。
如果员工 AA 可以和员工 BB 交流,员工 BB 可以和员工 CC 交流,那么也认为 AA 可以通过 BB 间接和 CC 交流。

现在,公司想花尽量少的钱,让任意一位员工都能(直接或间接)与任何其他员工进行交流

请你计算公司至少需要花费多少伯币。

输入格式

第一行包含两个整数 nnmm2n,m1002 \le n,m \le 100),分别表示员工人数和官方语言的数量。

接下来 nn 行,第 ii 行描述第 ii 位员工现在会的语言:

  • 这一行的第一个整数为 kik_i0kim0 \le k_i \le m),表示第 ii 位员工会的语言个数;
  • 接下来有 kik_i 个整数 ai1,ai2,,aikia_{i1}, a_{i2}, \dots, a_{ik_i}1aijm1 \le a_{ij} \le m),表示这些语言的编号。

保证同一名员工的语言列表中不会出现重复的语言编号。
注意,可能存在 ki=0k_i = 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

五名员工会的语言分别为:

  • 员工 11{2}\{2\}
  • 员工 22{2,3}\{2,3\}
  • 员工 33{3,4}\{3,4\}
  • 员工 44{4,5}\{4,5\}
  • 员工 55{5}\{5\}

可以发现,他们通过这些语言本身就已经“串成了一条链”,任意两人之间都可以通过若干中间人间接交流,因此不需要再额外学习语言,答案为 00

样例解释 #2

  • 员工 11:不会任何语言;
  • 员工 22{1,2,3}\{1,2,3\}
  • 员工 33{1}\{1\}
  • 员工 44{5,4}\{5,4\}
  • 员工 55{6,7}\{6,7\}
  • 员工 66{3}\{3\}
  • 员工 77{7,4}\{7,4\}
  • 员工 88{1}\{1\}

一种可行的最优方案是:

  • 让员工 11 学习语言 22
  • 让员工 88 学习语言 44

此时所有员工都会被连成一个整体,花费为 22,可以证明这是最小值。

样例解释 #3

  • 员工 11{2}\{2\}
  • 员工 22:不会任何语言。

只要让员工 22 学习语言 22,两人就可以直接交流,花费为 11。显然这是最优方案。

首页