UOJ Logo

NOI.AC

1S 512MB

#40. Erlang

统计

B. Erlang

题目描述

小W新学会了一种编程语言Erlang。小W知道Erlang是一个面向并发的程序设计语言,于是就开始拿它写并发的程序了。他写了一个程序,包含一个主进程和 $n$ 个子进程,每个子进程都在不断和主进程通信。按照程序的设定,每次通信都是由子进程给主进程传输一个数。

但是小W的程序现在出现了些偏差,他发现主进程结束不了了。原本的剧本是主进程收到任意一个子进程给它传输一个 $-1$ 就结束,他发现现在变成了主进程收到的所有数里面存在两个数相同,主进程才能结束。

他为了让自己的程序快点结束,他研究了一下那些进程。他发现第 $i$ 个子进程将要给主进程传输 $k_i$ 个数,分别是 $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$。他可以通过操作,控制主进程接受子进程传输的顺序。他每次可以选择一个还没传输完的所有的子进程 $x$,然后让主进程和子进程 $x$ 通信一次,子进程 $x$ 会从它剩下的数中随机选一个传输给主进程。他想要知道在最优策略下,他最坏要通信多少次才能让子进程结束。

一句话题意:现在一共有 $n$ 个可重集 $S_i$,小W每次可以选择一个非空的集合,然后从里面随机抽取一个数,然后把这个数从集合中删掉。当存在两次抽取出来的数相等时结束。小W想要最小化最坏情况下的操作次数。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行,每行第一个整数是 $k_i$,后面跟 $k_i$ 个整数,表示 $a_{i,j}$。

输出格式

输出一行表示最坏情况下的通信次数,若主进程不可能停下来,输出 $-1$。

样例1

input

6
3 1 2 3
1 1
1 2
1 3
1 4
1 5

output

2

explanation

先选第一个集合,如果是 $1$ 就选第 $2$ 个集合,如果是 $2$ 就选第 $3$ 个集合,如果是 $3$ 就选第 $4$ 个集合。

限制与约定

Subtask #1 (10 pts):$n \le 1, \sum k_i \le 10^5$

Subtask #2 (20 pts):$n \le 5, \sum k_i \le 10$

Subtask #3 (30 pts):$n, \sum k_i \le 1000$

Subtask #4 (40 pts):$n, \sum k_i \le 5*10^5$,$1 \le a_{i,j} \le 5*10^5$ 。

时间限制:1s

空间限制:512MB

下载

样例数据下载