题目描述Farmer John 的NNN头奶牛1≤N≤1051 \leq N \leq 10^51≤N≤105编号为1…N1 \ldots N1…N最近闲得发慌。因此她们发展了一个与 Farmer John 每天早上为她们挤牛奶时的排队顺序相关的复杂社会阶层。经过若干周的研究Farmer John 对他的奶牛的社会结构总计进行了MMM次观察1≤M≤50,0001 \leq M \leq 50,0001≤M≤50,000。每个观察结果都是某些奶牛的一个有序序列表示这些奶牛应该按照序列中的顺序进行挤奶。例如如果 Farmer John 的一次观察结果是序列222、555、111那么 Farmer John 应该在给奶牛555挤奶之前的某个时刻给奶牛222挤奶并在给奶牛111挤奶之前的某个时刻给奶牛555挤奶。Farmer John 的观察结果是按优先级排列的因此他的目标是最大化XXX的值使得他的挤奶顺序能够符合前XXX个观察结果描述的状态。当多种挤奶顺序都能符合前XXX个状态时Farmer John 遵循一个长期以来的传统——编号较小的奶牛的地位高于编号较大的奶牛因此他会最先给编号最小的奶牛挤奶。更正式地说如果有多个挤奶顺序符合这些状态Farmer John 会采用字典序最小的那一个。挤奶顺序xxx的字典序比挤奶顺序yyy小如果对于某个jjjxiyix_i y_ixi​yi​对所有iji jij成立并且xjyjx_j y_jxj​yj​即这两个挤奶顺序到某个位置之前完全相同而在该位置上xxx比yyy小。请帮助 Farmer John 确定给奶牛挤奶的最佳顺序。输入格式第一行包含NNN和MMM。接下来的MMM行每行描述了一个观察结果。第i1i1i1行描述了观察结果iii第一个数是观察结果中的奶牛数量mim_imi​后面是一列mim_imi​个整数给出这次观察中奶牛的顺序。所有mim_imi​的总和至多为200,000200,000200,000。输出格式输出NNN个空格分隔的整数表示一个1…N1 \ldots N1…N的排列为 Farmer John 给他的奶牛们挤奶应该采用的顺序。输入输出样例 #1输入 #14 3 3 1 2 3 2 4 2 3 3 4 1输出 #11 4 2 3说明/提示在这个例子中Farmer John 有四头奶牛他的挤奶顺序应该满足以下规则奶牛111在奶牛222之前、奶牛222在奶牛333之前第一个观察结果奶牛444在奶牛222之前第二个观察结果奶牛333在奶牛444之前、奶牛444在奶牛111之前第三个观察结果。前两个观察结果可以同时被满足但 Farmer John 不能同时满足所有规则因为这会要求奶牛111在奶牛333之前同时奶牛333在奶牛111之前。这意味着总共有两种可能的挤奶顺序1 4 2 31\ 4\ 2\ 31423和4 1 2 34\ 1\ 2\ 34123第一种是字典序较小的。题目来源Jay Leeds思路由于XXX满足单调性即XXX越小答案越能满足因此考虑二分XXX不难发现题中的每次观察可以转化成mim_imi​个点之间连边也就是每个点有一条连向下一个点的有向边每次二分完XXX后进行对前XXX个观察序列建图方法如上建完图后由于题目说每头牛必须有严格的先后顺序因此环是不符合答案的而建的图又为有向图所以直接用拓扑排序判图中是否存在环或者dfs顺便用一个数组记录拓扑序如果合法就暂时存到答案数组中这里还要注意由于题目要求输出字典序最小的序列所以拓扑排序的队列要变成优先队列小根堆难点这道题的核心是二分做题者需要注意到XXX的单调性但题目整体的难度不大AC code#includebits/stdc.husingnamespacestd;intn,m,in[100005],used[100005];vectorinta[100005],t,ans,head[100005];priority_queueint,vectorint,greaterintq;intcheck(intx){for(inti1;in;i){head[i].clear();}t.clear();memset(in,0,sizeof(in));memset(used,0,sizeof(used));for(inti1;ix;i){for(intj0;ja[i].size();j){if(j!0){head[a[i][j-1]].push_back(a[i][j]);in[a[i][j]];}}}for(inti1;in;i){sort(head[i].begin(),head[i].end());}for(inti1;in;i){if(in[i]0){q.push(i);}}while(!q.empty()){intuq.top();q.pop();t.push_back(u);for(inti0;ihead[u].size();i){intvhead[u][i];in[v]--;if(in[v]0){q.push(v);}}}if(t.size()!n){return0;}anst;return1;}intmain(){cinnm;for(inti1;im;i){intl;cinl;for(intj1;jl;j){intx;cinx;a[i].push_back(x);}}intl0,rm;while(lr){intmid(lr)/2;if(check(mid)){lmid1;}else{rmid-1;}}if(ans.empty()){for(inti1;in;i){couti ;}return0;}for(inti0;ians.size();i){coutans[i] ;}return0;}