车站分级-题解

查看原题戳这里

一道有趣的建图题

qxy当时做了好久才发现自己图建错了qwq
看到“如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠”后，大家有没有感到一丝丝熟悉呢？

没错，这个条件和拓扑排序的条件很相似

所以，我们只需要把所有的车站放到一个图中，在用一个类似于拓扑排序的算法去更新答案就可以了。

那么，具体该怎么建图呢？

建图是这个题的难点，但其实原理非常简单。

首先，对于每一班车，它提供的信息只对它的起点(a)到终点(b)这一段有效而并非对全部有效。
其次，因为“如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠”，所以在区间[a,b]中这趟车停过的点的级别一定高于没有停的点的级别。根据拓扑排序的要求，我们只需要从没有停下的点向每一个停下的点连一条有向边就可以了。
ps：为了卡你，出题人一定对把图搞得很稠密，所以存图的时候需要优化一下时间复杂度。
附一下代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std; 
int head,tail,n,s,Max,t,m,c[1001],bus[1001],f[1001][1001],que[1001],d[1001],u[1001],stop[1001];
void work()
{
    while(head < tail)
    {
        head++;
        for(int i = 1; i <= n; i++)
            if(f[que[head]][i])
            {
                d[i] –;
                u[i] = u[que[head]] + 1;
                Max = max(Max,u[i]);
                if(d[i] == 0) que[++tail] = i;
            }
    }
}
int main()
{
    scanf(“%d%d”,&n,&m);
    for(int i = 1; i <= n; i++) u[i] = 0x7fffffff;
    for(int i = 1; i <= m; i++)
    {
        scanf(“%d”,&s);
        memset(c,0,sizeof(c)); t = 0;
        for(int j = 1; j <= s; j++) scanf(“%d”,&bus[j]);
        for(int j = 1; j <= s; j++) c[bus[j]] = 1;
        for(int j = bus[1]; j <= bus[s]; j++) if(!c[j]) stop[++t] = j;
        for(int j = 1; j <= s; j++)
            for(int k = 1; k <= t; k++)
            {
                if(!f[stop[k]][bus[j]])  //没连边
                {
                    f[stop[k]][bus[j]] = 1;
                    d[bus[j]] ++;
                }
            }
    }
    for(int i = 1; i <= n; i++)
        if(!d[i]) {
            que[++tail] = i;
            u[i] = 1;
        }
    work();
    printf(“%d”,Max);
    return 0;
}