A91470.最少学习费用

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

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

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

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

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

输入格式

第一行包含两个整数 nn 和 mm(2≤n,m≤1002 \le n,m \le 100),分别表示员工人数和官方语言的数量。

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

  • 这一行的第一个整数为 kik_i(0≤ki≤m0 \le k_i \le m),表示第 ii 位员工会的语言个数;
  • 接下来有 kik_i 个整数 ai1,ai2,…,aikia_{i1}, a_{i2}, \dots, a_{ik_i}(1≤aij≤m1 \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。显然这是最优方案。

输入解题思路,AI测评打分。不知道怎么写?

首页