简答题
偏难
#23637
车站分级 【问题描述】 一条单向的铁路线上,依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别,最低为 1 级。现有若干趟车次在这条线…
车站分级
【问题描述】
一条单向的铁路线上,依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别,最低为 1 级。现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 x,则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。(注意:起始站和终点站自然也算作事先已知需要停靠的站点)
例如,下表是 5 趟车次的运行情况。其中,前 4 趟车次均满足要求,而第 5 趟车次由于停靠了 3 号火车站(2 级)却未停靠途经的 6 号火车站(亦为 2 级)而不满足要求。

现有 m 趟车次的运行情况(全部满足要求),试推算这 n 个火车站至少分为几个不同的级别。
【输入】
输入文件为 level.in。
第一行包含 2 个正整数 n, m,用一个空格隔开。
第 i + 1 行(1 ≤ i ≤ m)中,首先是一个正整数 si(2 ≤ si ≤ n),表示第 i 趟车次有 si 个停靠站;接下来有 si个正整数,表示所有停靠站的编号,从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。
【输出】
输出文件为 level.out。
输出只有一行,包含一个正整数,即 n 个火车站最少划分的级别数。
【输入输出样例】

【数据范围】
对于 20%的数据,1 ≤ n, m ≤ 10;
对于 50%的数据,1 ≤ n, m ≤ 100;
对于 100%的数据,1 ≤ n, m ≤ 1000。
答案与解析
正确答案:<p style="text-align: left;">#include<bits/stdc++.h></p><p style="text-align: left;">#define in read()</p><p style="text-align: left;">#define N 10009</p><p style="text-align: left;">#define M 9000009 </p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">inline char nc(){</p><p style="text-align: left;"> static char buf[100000],*p1=buf,*p2=buf;</p><p style="text-align: left;"> return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline int read(){</p><p style="text-align: left;"> char ch=nc();int sum=0;</p><p style="text-align: left;"> while(!(ch>='0'&&ch<='9'))ch=nc();</p><p style="text-align: left;"> while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();</p><p style="text-align: left;"> return sum;</p><p style="text-align: left;">}</p><p style="text-align: left;">int n,m,du[N],chu[N];</p><p style="text-align: left;">int nxt[M],to[M],head[N],cnt=0;</p><p style="text-align: left;">void add(int x,int y){nxt[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}</p><p style="text-align: left;">int s[N],g[1009][1009],dis[N];</p><p style="text-align: left;">bool vis[1009];</p><p style="text-align: left;">int main(){</p><p style="text-align: left;"><span style="white-space:pre"> </span>n=in;m=in;</p><p style="text-align: left;"><span style="white-space:pre"> </span>int i,j,k;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(i=1;i<=m;++i){</p><p style="text-align: left;"><span style="white-space:pre"> </span>k=in;</p><p style="text-align: left;"><span style="white-space:pre"> </span>memset(vis,0,sizeof(vis));</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(j=1;j<=k;++j){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int hh=in;</p><p style="text-align: left;"><span style="white-space:pre"> </span>s[j]=hh;vis[hh]=1;<span style="white-space:pre"> </span></p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(j=s[1];j<=s[k];++j){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!vis[j]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int p=1;p<=k;++p){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!g[s[p]][j]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>g[s[p]][j]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>add(s[p],j);</p><p style="text-align: left;"><span style="white-space:pre"> </span>du[j]++;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>queue<int> q;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(i=1;i<=n;++i)</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!du[i]) dis[i]=1,q.push(i);</p><p style="text-align: left;"><span style="white-space:pre"> </span>int ans=-1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(!q.empty()){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int u=q.front();q.pop();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int e=head[u];e;e=nxt[e]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int v=to[e];</p><p style="text-align: left;"><span style="white-space:pre"> </span>dis[v]=dis[u]+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ans=max(ans,dis[v]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>du[v]--;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!du[v]) q.push(v);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>cout<<ans;</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。