P4376 [USACO18OPEN]Milking Order

    • 381通过
    • 1.2K提交
  • 题目提供者 Cherryblossom
  • 评测方式 云端评测
  • 标签 二分答案 图的建立,建图 拓扑排序 排序 USACO 2018
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Farmer John的$N$头奶牛($1 \leq N \leq 10^5$),仍然编号为$1 \ldots N$,正好闲得发慌。因此,她们发展了一个与Farmer John每天早上为她们挤牛奶的时候的排队顺序相关的复杂的社会阶层。

    经过若干周的研究,Farmer John对他的奶牛的社会结构总计进行了$M$次观察($1 \leq M \leq 50,000$)。每个观察结果都是他的某些奶牛的一个有序序列,表示这些奶牛应该以与她们在序列中出现的顺序相同的顺序进行挤奶。比方说,如果Farmer John的一次观察结果是序列2、5、1,Farmer John应该在给奶牛5挤奶之前的某个时刻给奶牛2挤奶,在给奶牛1挤奶之前的某个时刻给奶牛5挤奶。

    Farmer John的观察结果是按优先级排列的,所以他的目标是最大化$X$的值,使得他的挤奶顺序能够符合前$X$个观察结果描述的状态。当多种挤奶顺序都能符合前$X$个状态时,Farmer John相信一个长期以来的传统——编号较小的奶牛的地位高于编号较大的奶牛,所以他会最先给编号最小的奶牛挤奶。更加正式地说,如果有多个挤奶顺序符合这些状态,Farmer John会采用字典序最小的那一个。挤奶顺序$x$的字典序比挤奶顺序$y$要小,如果对于某个$j$,$x_i = y_i$对所有$i < j$成立,并且$x_j < y_j$(也就是说,这两个挤奶顺序到某个位置之前都是完全相同的,在这个位置上$x$比$y$要小)。

    请帮助Farmer John求出为奶牛挤奶的最佳顺序。

    输入输出格式

    输入格式:

    第一行包含$N$和$M$。接下来的$M$行,每行描述了一个观察结果。第$i+1$行描述了观察结果$i$,第一个数是观察结果中的奶牛数量$m_i$,后面是一列$m_i$个整数,给出这次观察中奶牛的顺序。所有$m_i$的和至多为$200,000$。

    输出格式:

    输出$N$个空格分隔的整数,给出一个$1 \ldots N$的排列,为Farmer John给他的奶牛们挤奶应该采用的的顺序。

    输入输出样例

    输入样例#1: 复制
    4 3
    3 1 2 3
    2 4 2
    3 3 4 1
    输出样例#1: 复制
    1 4 2 3
    

    说明

    这里,Farmer John有四头奶牛,他的挤奶顺序应该是奶牛1在奶牛2之前、奶牛2在奶牛3之前(第一个观察结果),奶牛4在奶牛2之前(第二个观察结果),奶牛3在奶牛4之前、奶牛4在奶牛1之前(第三个观察结果)。前两个观察结果可以同时被满足,但是Farmer John不能同时满足所有的规则,因为这样的话会要求奶牛1在奶牛3之前,同时奶牛3在奶牛1之前。

    这意味着总共有两种可能的挤奶顺序:1 4 2 3和4 1 2 3,第一种是字典序较小的。

    供题:Jay Leeds

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。