现有m趟车次的运行亚博集团情况(2个正整数级别

亚博集团标题说明

单程铁路线的火车站依次编号为 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;
}

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.zh-map.com/a/ganhuo/631.html