#PU838. USACO 2018 US Open Contest, Gold — Problem 2. Milking Order

    ID: 1596 传统题 文件IO:milkorder 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:open18来源:usaco.orgscoring:equal_test_cases拓扑排序

USACO 2018 US Open Contest, Gold — Problem 2. Milking Order

USACO 2018 US Open Contest, Gold — Problem 2. Milking Order

题目描述

Farmer John's NN cows (1≤N≤1051 \leq N \leq 10^5), numbered 1…N1 \ldots N as always, happen to have too much time on their hooves. As a result, they have worked out a complex social hierarchy related to the order in which Farmer John milks them every morning. After weeks of study, Farmer John has made MM observations about his cows' social structure (1≤M≤50,0001 \leq M \leq 50,000). Each observation is an ordered list of some of his cows, indicating that these cows should be milked in the same order in which they appear in this list. For example, if one of Farmer John's observations is the list 2, 5, 1, Farmer John should milk cow 2 sometime before he milks cow 5, who should be milked sometime before he milks cow 1. Farmer John's observations are prioritized, so his goal is to maximize the value of XX for which his milking order meets the conditions outlined in the first XX observations. If multiple milking orders satisfy these first XX conditions, Farmer John believes that it is a longstanding tradition that cows with lower numbers outrank those with higher numbers, so he would like to milk the lowest-numbered cows first. More formally, if multiple milking orders satisfy these conditions, Farmer John would like to use the lexicographically smallest one. An ordering xx is lexicographically smaller than an ordering yy if for some jj, xi=yix_i = y_i for all i<ji < j and xj<yjx_j < y_j (in other words, the two orderings are identical up to a certain point, at which xx is smaller than yy). Please help Farmer John determine the best order in which to milk his cows.

输入格式

The first line contains NN and MM. The next MM lines each describe an observation. Line i+1i+1 describes observation ii, and starts with the number of cows mim_i listed in the observation followed by the list of mim_i integers giving the ordering of cows in the observation. The sum of the mim_i's is at most 200,000200,000.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4 3
3 1 2 3
2 4 2
3 3 4 1
1 4 2 3
Here, Farmer John has four cows and should milk cow 1 before cow 2 and cow 2
before cow 3 (the first observation), cow 4 before cow 2 (the second
observation), and cow 3 before cow 4 and cow 4 before cow 1 (the third
observation).   The first two observations can be satisfied simultaneously, but
Farmer John cannot meet all of these criteria at once, as to do so would require
that cow 1 come before cow 3 and cow 3 before cow 1.
This means there are two possible orderings: 1 4 2 3 and 4 1 2 3, the first
being lexicographically smaller.
Problem credits: Jay Leeds