亚博集团标题说明
单程铁路线的火车站依次编号为 1,2,…,n。每个火车站都有一个等级,最低为1级。这条线路上运行的列车有几列,每列满足以下要求:如果该列车停靠在火车站x中国最长的铁路车次,则始发站和始发站之间的所有列车级别大于等于火车站x的终点站必须停车。 . (注:起点站和终点站自然算作需要提前停站的已知站)
例如,下表显示了 5 列火车的运行情况。其中,前4列符合要求中国最长的铁路车次,而第5列不符合要求,因为它停靠在3号火车站(2级),但没有停靠在经过的6号火车站(也是2级)。
亚博集团现有m个列车的运行情况(均符合要求),试算出这n个列车站至少分为几个不同的层级。
输入格式
第一行包含 2 个正整数 n,m中国最长的铁路车次,用空格隔开。
亚博集团在第i+1行(1≤i≤m)中国最长的铁路车次,第一个是正整数si(2≤si≤n),表示第i次列车有si站;那么有si个正整数,表示所有停靠点的个数,从小到大排列。用空格分隔每两个数字。输入以确保所有行程都符合要求。
输出格式
一个正整数,即最小级别数除以n个火车站。
亚博集团想法:当uuu的层级小于vvv的层级时,我们连接一条从uuu到vvv的有向边,最后得到一个有向无环图(因为数据符合要求)中国最长的铁路车次,其实答案是这条DAGDAGDAG最长的路。那么拓扑排序+dpdpdp就可以了。
亚博集团
#include
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pr pair
using namespace std;
typedef long long ll;
const int maxn=1005;
bool vis[maxn];
int a[maxn],deep[maxn],ind[maxn],Stack[maxn];
int s[maxn][maxn];
int n,m,top;
void topo()
{
top=0;
for(int i=1;i<=n;i++)
if(ind[i]==0)
Stack[++top]=i;
int tmp,ans=0;
while(top)
{
tmp=Stack[top--];
ans=max(ans,deep[tmp]);
for(int i=1;i<=n;i++)
{
if(s[tmp][i])
{
--ind[i];
deep[i]=max(deep[i],deep[tmp]+1);
if(ind[i]==0)
Stack[++top]=i;
}
}
}
printf("%d\n",ans+1);
}
int main()
{
scanf("%d %d",&n,&m);
int len=0;
for(int i=0;i<m;i++)
{
scanf("%d",&len);
for(int j=1;j<=len;j++)
scanf("%d",&a[j]),vis[a[j]]=1;
for(int j=a[1];j<=a[len];j++)
{
if(vis[j])
{
vis[j]=0;
continue;
}
for(int k=1;k<=len;k++)
if(!s[j][a[k]])
s[j][a[k]]=1,++ind[a[k]];
}
}
topo();
return 0;
}