本题是2013年NOIP普及组的压轴题

差分约束裸题。
计算当前线路中最小的级别（比较始发站和终点站）。
整条线路中所有大于这个级别的都必须停靠
所有未停靠的站点的级别一定小于这个级别

也就是说所有未停靠的即为级别低，记为A
所有停靠的站点级别一定比A的高，记作B
得到公式$B\ge A+1$
根据很明显是一道差分约束问题。
根据差分约束的概念，我们从所有的A向所有的B连一条权值为1的有向边。

然后根据差分约束的套路，我们还要设一个界限才能求出最大值。

因为所有车站级别都是正值，所以$A\ge 1$，也就是从0向所有的A中的点连一条权值为1 的有向边。我们常常用直接给dist数组赋值为1代替。

但是由于实际数据范围较大

最坏情况下是有1000趟火车，每趟有1000个点，每趟上限有500个点停站，则有(1000 - 500)个点不停站，不停站的点都向停站的点连有向边，则总共有 $500\ast 500\ast 1000=2.5\ast 10^8$，差分约束的spfa有可能超时。

由于本题中的所有点的权值都是大于0，并且一定满足要求$=>$所有车站都等级森严$=>$不存在环$=>$可以拓扑排序得到拓扑图使用递推求解差分约束问题。

因此整体的思路为：

• 拓扑排序得拓扑图
• “至少”$=>$要求的是最小值$=>$所有条件的下界中取最大值$=>$最长路，因此我们，根据拓扑序跑最长路递推即可。
• 答案为满足所有约束条件的解中最大值既是题目要求的最高的级别

一个建图的优化：

如果直接暴力建图就会建$O(nm)$条边，也就是$2\ast 10^8$个点，时间和空间都有可能超时。

我们可以在中间建一个虚拟节点，左边向虚拟点连0，虚拟点向右边连1等价于左边向右边连1

这样只会建$O(n+m)$条边

注意的是本题一共m条线路,每条线路一个虚拟源点,所以一共会有n + m 个点。

当年出题人并没有卡这一点，不然要卡死一大批有志青年

如下图所示：

优化前：

然后就是代码了

别忘了一共有n + m 个点

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>using namespace std;const int N = 2007, M = 5000007;int n, m;
int ver[M], nex[M], edge[M], head[N], tot;
int din[N];
int vis[N];
int q[N];
int dist[N];void add(int x, int y, int z){ver[tot] = y;edge[tot] = z;nex[tot] = head[x];head[x] = tot ++ ;din[y] ++ ;
}void toposort(){int hh = 0, tt = -1;for(int i = 1;i <= n + m;++i){//一共n + m个点,要遍历所有的点if(!din[i]){q[++ tt] = i;if(tt == N)tt = 0;}}while(hh <= tt){int x = q[hh ++ ];if(hh == N)hh = 0;for(int i = head[x];~i;i = nex[i]){int y = ver[i];if(-- din[y] == 0){q[++ tt] = y;if(tt == N)tt = 0;}}}
}int main(){scanf("%d%d", &n,&m);memset(head,-1,sizeof head);for(int i = 1;i <= m;++i){memset(vis,0,sizeof vis);int t,stop;scanf("%d",&t);int start = n, end = 1;while(t -- ){scanf("%d",&stop);//输入的是编号start = min(start, stop);end = max(end, stop);vis[stop] = true;//代表该站要停靠.}int source = n + i;//n + 1for(int j = start;j <= end;++j){//该线路上的所有经过的站点的编号一定在始发站和终点站之间if(vis[j])//要停靠,说明是右部点add(source, j, 1);else add(j, source, 0);}}toposort();for(int i = 1;i <= n;++i)//A ≥ 1dist[i] = 1;for(int i = 0;i < n + m;++i){//手写的队列是从0开始的int x = q[i];for(int j = head[x];~j;j = nex[j]){int y = ver[j], z = edge[j]; dist[y] = max(dist[y], dist[x] + z);}}int res = 0;for(int i = 1;i <= n;++i)//满足所有约束条件的解中最大值既是题目要求的最高的级别res = max(res, dist[i]);printf("%d\n",res);return 0;
}