洛谷P1983 [NOIP2013 普及组] 车站分级 题解

题目链接：P1983 [NOIP2013 普及组] 车站分级

题意：

一条单向的铁路线上，依次有编号为 $1, 2,, n $ 的 \(n\) 个火车站。每个火车站都有一个级别，最低为 \(1\) 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 \(x\)，则始发站、终点站之间所有级别大于等于火车站 \(x\) 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）

例如，下表是 \(5\) 趟车次的运行情况。其中，前$ 4$ 趟车次均满足要求，而第 \(5\) 趟车次由于停靠了 \(3\) 号火车站（ \(2\) 级）却未停靠途经的 \(6\) 号火车站（亦为 \(2\) 级）而不满足要求。

现有 \(m\) 趟车次的运行情况（全部满足要求），试推算这 \(n\) 个火车站至少分为几个不同的级别。

对于 \(100\%\) 的数据，\(1 \le n, m \le 1000\)。

考虑建图。

对于一趟车，我们把所有「不停靠的站」向「停靠的站」连一条有向边

即边 \(u \to v\) 表示 \(u\) 的级别在 \(v\) 之前。然后跑一遍 toposort 就好了

时间复杂度 \(O(n^2)\) 感觉有点水，应该还可以加强的。

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
#include <bitset>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e3+15)

bitset<N> bi; queue<int> q;
int n,m,pos,res,a[N],tmp[N],g[N][N],in[N],f[N];
void topo()
{
    for(int i=1; i<=n; i++)
        if(!in[i]) q.push(i);
    fill(f+1,f+1+n,1);
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(int i=1; i<=n; i++)
        {
            if(!g[u][i]) continue;
            if(!(--in[i]))
                f[i]=max(f[i],f[u]+1),q.push(i);
        }
    }
    cout << *max_element(f+1,f+1+n) << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,t; i<=m; i++)
    {
        bi=0; cin >> t;
        for(int j=1; j<=t; j++)
            cin >> a[j],bi[a[j]]=1;
        for(int j=a[1]; j<=a[t]; j++)
        {
            if(bi[j]) continue;
            for(int k=1; k<=t; k++)
                if(!g[j][a[k]]) g[j][a[k]]=1,++in[a[k]];
        }
    } topo();
    return 0;
}