#XMOJ12649. 奇妙市场
奇妙市场
说明
时间限制:1 Sec
内存限制:256 MB
输入文件:market.in 输出文件:market.out
奇妙市场是一条只有单一直线通道的超市。
市场里一共有 $n$ 种商品,编号 $1$ 到 $n$,每种商品恰好一个,不存在重复商品。
沿着通道从入口到出口依次摆放着 $n$ 个货架,每个货架上可以放任意一种 $1 \sim n$ 的商品。
顾客必须沿着货架从入口往出口单向走,不能回头,并且市场有下面两条特殊规则:
- 如果走到商品 $g_i$ 所在货架之前,顾客的购物篮里已经集齐了 $h_{i,1},h_{i,2},\dots,h_{i,r_i}$ 全部商品,那么顾客经过这个货架时,必须把 $g_i$ 放进购物篮。
- 对于没有上述条件约束的商品,顾客经过它的货架时,必须把它放进购物篮。
给定货架与商品总数 $n$,以及 $m$ 条商品的约束条件。
你可以自由安排商品在货架上的摆放顺序,求最多能让多少种商品被顾客拿进购物篮。
输入格式
第一行两个整数 $n,m$。
接下来 $m$ 组数据,每组数据两行:
第一行两个整数 $g_i,r_i$。
第二行 $r_i$ 个整数 $h_{i,1},h_{i,2},\dots,h_{i,r_i}$。
输出格式
输出在最优摆放方案下,可以被拿进购物篮的商品数量的最大值。
样例
样例 1
10 8
7 1
8
10 1
3
9 3
3 4 10
5 2
8 4
2 3
7 1 10
4 2
7 6
6 2
1 3
1 2
7 3
10
样例说明:
存在合适的摆放顺序,可以让全部商品都被放进购物篮。
样例 2
8 7
2 1
1
8 1
1
3 2
2 8
4 1
3
5 2
3 6
6 3
3 4 7
7 1
5
5
样例说明:
最优摆放下最多只能让 种商品被放进购物篮。
数据范围
对于 30% 的数据,$n \le 16$。
对于 100% 的数据,$1 \le n \le 500$,$0 \le m \le n$,$1 \le g_i \le n$,$1 \le r_i \le 32$,$1 \le h_{i,j} \le n$。
对于 100% 的数据,满足同一条约束内的 $h_{i,j}$ 互不相同,所有 $g_i$ 互不相同,保证 $g_i$ 不会出现在自己对应的 $h_{i,j}$ 里面。没有出现在 $g_i$ 里的商品,属于无条件必须被放入购物篮的商品。
相关
在下列比赛中: