车站分级：很好的拓扑排序题，细节有点多。
图论建模
首先观察对于一条线路，我们可以从中直接得到什么信息：
假设这条线路的开头为 \(st\) ，结尾为 \(ed\) ，那么在 \([st,ed]\) 的车站中，没有被选入线路的点一定比选入线路的点的 级数 至少 少 \(1\) 。
对于这一点条件，我们就可以建模了。
和差分约束一样，我们从某个点起连到所有比其多 \(1\) 的点的有向边，边权赋为 \(1\) 。
然后拓扑排序跑最长路即可。不是最短路的原因是 这些都是充分必要条件，每一个都必须满足，因此要选最长路。
这样建图是 \(O(n^2m)\) 的，虽然常数小，但还是容易被卡。
优化
发现复杂度瓶颈在于是一堆点往一堆点连边，所以我们从优化建边的方式入手：虚点优化。
我们把那些原来的起点们连多条向这个虚点的有向边，边权赋为 \(0\) ；然后从这个虚点连多条向原来的终点们的有向边，边权赋为 \(1\) ，这样就可以在 \(O(n)\) 的时间里完成 \(O(n^2)\) 的建边了。
总体复杂度是 \(O(nm)\) 。
细节
边权全部赋值为 \(1\) 的做法
对于这种做法，非常万能，但不是常人的思维。
写这种做法细节很少，我们无需处理起点是 \(0\) 是 \(1\) ，直接全赋为 \(0\) 就好了，因为我们先不考虑起点。
最后统计答案的时候，我们只需要将 $ ans / 2 +1$ 即可， \(/2\) 是因为经过虚点一次会走两条边，要除回来；\(+1\) 是因为要加上起点。
同时注意有可能虚点入度为 \(0\) ，所以虚点也要加入拓扑排序的初始化中，比如下面的数据：
in:
3 1
2 1 2
out:
1
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[1005],dp[3005],rd[3005],ans=0;
vector<int>g[3005];
queue<int>q;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int s,st=0,ed=0;
cin>>s;
bitset<1005>isin;
for(int j=1;j<=s;j++)
{
cin>>a[j];
isin[a[j]]=1;
if(j==1)st=a[j];
if(j==s)ed=a[j];
}
int vt=n+i;
for(int j=st;j<=ed;j++)
{
if(isin[j]==0)
{
g[j].push_back(vt);
rd[vt]++;
}
else
{
g[vt].push_back(j);
rd[j]++;
}
}
}
for(int i=1;i<=n+m;i++)
{
if(rd[i]==0)
{
q.push(i);
dp[i]=0;
}
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(auto v:g[u])
{
dp[v]=max(dp[v],dp[u]+1);
rd[v]--;
if(rd[v]==0)
{
q.push(v);
}
}
}
for(int i=1;i<=n+m;i++)
{
ans=max(ans,dp[i]/2+1);
}
cout<<ans;
return 0;
}
对于上面那种边权先赋为 \(1\) ，后面再赋为 \(0\) 的做法
依然是上面的那个 hack 数据：
in:
3 1
2 1 2
out:
1
如果把入度为 \(0\) 的虚点的最长路也初始化为 \(1\) 的话，就会导致这组数据结果多一个 \(1\)。因此应该把虚点初始化为 \(0\) ，其他点初始化为 \(1\) 。
另外，不要读错题了，只有起点和终点之间的车站才受分级的约束，而不是全部车站。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[1005],dp[3005],rd[3005],ans=0;
struct edge{
int to,w;
};
vector<edge>g[3005];
queue<int>q;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int s,st=0,ed=0;
cin>>s;
bitset<1005>isin;
for(int j=1;j<=s;j++)
{
cin>>a[j];
isin[a[j]]=1;
if(j==1)st=a[j];
if(j==s)ed=a[j];
}
int vt=n+i;
for(int j=st;j<=ed;j++)
{
if(isin[j]==0)
{
g[j].push_back({vt,0});
rd[vt]++;
}
else
{
g[vt].push_back({j,1});
rd[j]++;
}
}
}
for(int i=1;i<=n;i++)
{
if(rd[i]==0)
{
q.push(i);
dp[i]=1;
}
}
for(int i=n+1;i<=n+m;i++)
{
if(rd[i]==0)
{
q.push(i);
dp[i]=0;
}
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(auto tmp:g[u])
{
int v=tmp.to,w=tmp.w;
dp[v]=max(dp[v],dp[u]+w);
rd[v]--;
if(rd[v]==0)
{
q.push(v);
}
}
}
for(int i=1;i<=n+m;i++)
{
ans=max(ans,dp[i]);
}
cout<<ans;
return 0;
}
/*
3 1
2 1 2
*/