这道题根据题意，能得出该结论：
·一条线路经过的站点，停靠站点等级一定大于未停靠的站点
又因为输入保证所有的车次都满足要求，所以满足偏序集关系。我们可以将站点的大小关系用$DAG$图表示，即将一条线路中停靠站点向未停靠站点连有向边。最后求一遍DAG图中最长链。
问题在于构图的复杂度为$O(n^2m)$，无法接受。
这里采用构建虚点的方式解决构图问题，如下图
此时复杂度为$O(nm)$。
最后注意最长链包括了虚点，把它去掉即可。
1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 #define re register10 #define rep(i, a, b) for (re int i = a; i <= b; ++i)11 #define repd(i, a, b) for (re int i = a; i >= b; --i)12 #define maxx(a, b) a = max(a, b);13 #define minn(a, b) a = min(a, b);14 #define LL long long15 #define inf (1 << 30)16 17 inline int read() {18 int w = 0, f = 1; char c = getchar();19 while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar();20 while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar();21 return w * f;22 }23 24 queue q, q0, empty;25 26 const int maxn = 1e3 + 5;27 28 int a[maxn][maxn], e[maxn << 1][maxn << 1], n, m, r[maxn], d[maxn << 1], ans;29 30 int main() {31 n = read(), m = read();32 33 rep(i, 1, m) {34 a[i][0] = read();35 memset(r, 0, sizeof(r));36 rep(j, 1, a[i][0]) a[i][j] = read(), r[a[i][j]] = 1;37 rep(j, a[i][1], a[i][a[i][0]]) if (r[j]) e[j][n+i] = 1; else e[n+i][j] = 1;38 }39 40 rep(i, 1, n+m) {41 rep(j, 1, n+m)42 d[i] += e[j][i] ? 1 : 0;43 if (!d[i]) q.push(i);44 }45 46 while (!q.empty()) {47 while (!q.empty()) {48 int u = q.front(); q.pop();49 rep(i, 1, n+m) if (e[u][i]) {50 d[i]--;51 if (!d[i]) q0.push(i);52 }53 }54 q = q0; q0 = empty;55 ans++;56 }57 58 printf("%d", (ans + 1) >> 1);59 60 return 0;61 }