3048: 【普及+/提高】【P1983】车站分级
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：4
解决：4
题目描述
一条单向的铁路线上，依次有编号为 的 个火车站。每个火车站都有一个级别，最低为 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 ，则始发站、终点站之间所有级别大于等于火车站 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）
例如，下表是趟车次的运行情况。其中，前 趟车次均满足要求，而第 趟车次由于停靠了 号火车站（ 级）却未停靠途经的 号火车站（亦为 级）而不满足要求。
现有 趟车次的运行情况（全部满足要求），试推算这 个火车站至少分为几个不同的级别。
输入
第一行包含 个正整数 ，用一个空格隔开。
第 行中，首先是一个正整数 ，表示第 趟车次有 个停靠站；接下来有个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。
输出
一个正整数，即 个火车站最少划分的级别数。
样例输入 复制
9 2
4 1 3 5 6
3 3 5 6 样例输出 复制
2提示
对于的数据，；
对于 的数据，；
对于 的数据，。
这道题我们可以理解为凡是停靠过的站，那么这个站就比没停靠过的站级别高。
做出一张图（A指向B表示A车站级别大于B车站）[用的是样例1]
#include <bits/stdc++.h>
using namespace std;
/**
思路：停靠站->非停靠站连边，然后用拓扑排序求深度。
*/
const int N = 1010; //题目中要求结点数是1000个上限
int n, m; //n个车站,m个车次
vector<int> edge[N]; //邻接表
int in[N]; //入度数组
bool flag[N]; //flag[i]标识i是不是停靠站点
bool st[N][N]; //用来判断是不是已经存在了i到j的边
int ans; //答案
int a[N]; //停靠站信息
//结构体，携带两个信息，一个是哪个车站，另一个是几级
struct Node {
int num;
int step;
};
//拓扑排序，计算出层次
void topSort() {
//拓扑排序
queue<Node> q; //拓扑用队列
//查找所有入度为0的结点入队列,第一个参数是结点号，第二个参数是步数
for (int i = 1; i <= n; ++i) if (!in[i]) q.push({i, 1});
//开始拓扑套路
while (!q.empty()) {
//结点ID
int u = q.front().num;
//步数
int step = q.front().step;
q.pop();
//注意修改ans的值，保持最大值
ans = max(ans, step);
for (auto v:edge[ u ]) {
in[v]--;
if (!in[v]) q.push({v, step + 1});
}
}
}
int main() {
cin >> n >> m;
while (m--) {
//每次重新初始化状态数组
memset(flag, 0, sizeof(flag));
int s; //本轮的停靠站数量
cin >> s;
//读入停靠站信息
for (int i = 1; i <= s; ++i) cin >> a[i], flag[a[i]] = true; //标识是停靠站
//遍历出发站到终点站,这里可不是全部车站啊！只有在范围内的才能明确等级关系啊！！！注意
//这里a[1]是指起点，a[ s ]是指终点，就是这个车次的出发点到结束点，这中间有停靠的，有不停靠的，
// 不停靠的站等级一定是小于停靠的
for (int i = a[1]; i <= a[ s ]; ++i)
//如果不是停靠站，那就是等级低的站，需要连边~,停靠站->非停靠站连边
if (!flag[i]) {
int target = i;
for (int j = 1; j <= s; ++j) {
int source = a[j];
if (!st[source][target]) {//没配置过边的有效，重边只留一条.因为不同的车次，
// 存在两条一样的边是很正常的，但没有必要保留多个。
edge[source].push_back(target);
st[source][target] = true;//标识已配置
in[target]++;//入度++
}
}
}
}
//拓扑排序
topSort();
//输出结果
cout << ans << endl;
return 0;
}
/*
因为火车都要停靠比它高级（大于等于）的车站，所以其它不停的就是比它级别小（小于）的车站，现在求最高等级的车站是几级。
在所有不停的站的级别小于停靠的站的情况下，我们可以做出一张图（A指向B表示A车站级别大于B车站）
*/
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1010
int n,m,ans=1;
vector <int> p[MAXN];
bool b[MAXN],c[MAXN][MAXN]; //b[i]表示是否是停靠站, c[i][j]表示j>i的级别
int a[MAXN],outd[MAXN],ind[MAXN];
struct node {
int x,d;
};
queue <node> q;
int main(){
cin >> n >> m;
for (int i = 0;i < m; i++) {
int s;
cin >> s;
memset(b,0,sizeof(b));
for (int j = 1; j <= s; j++) {
cin >> a[j];
b[a[j]] = true;
}
for (int j = a[1]; j <= a[ s ]; j++) {
if (!b[j]) { //枚举站点，若不是已停靠的就小于所有停靠站的等级
for (int k = 1; k <= s; k++) { //枚举已停靠站点
if (!c[j][a[k]]) { //没配置过边的有效，重边只留一条.因为不同的车次，存在两条一样的边是很正常的，但没有必要保留多个。
c[j][a[k]] = true;
outd[a[k]]++;
ind[j]++;
p[a[k]].push_back(j);
}
}
}
}
}
for (int i = 1;i <= n; i++) {
if (ind[i] == 0) {
q.push((node){i,1});
}
}
while (!q.empty()) {
node t=q.front();
q.pop();
if (outd[t.x] == 0 ) {
ans = max(ans, t.d);
}
for (int i = 0, sz = p[t.x].size(); i < sz ; i++) {
ind[p[t.x][i]]--;
if (ind[p[t.x][i]] == 0 ) {
q.push((node){p[t.x][i], t.d+1});
}
}
}
cout << ans <<endl;
return 0;
}