91 lines
3.1 KiB
C++
91 lines
3.1 KiB
C++
|
#include <bits/stdc++.h>
|
|||
|
|
|
|||
|
|
using namespace std;
|
|||
|
|
const int N = 2010, M = 1000010;
|
|||
|
|
const int INF = 0x3f3f3f3f;
|
|||
|
|
int n, m;
|
|||
|
|
int in[N];
|
|||
|
|
int d[N];
|
|||
|
|
int st[N];
|
|||
|
|
|
|||
|
|
// 邻接表
|
|||
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|||
|
|
void add(int a, int b, int c) {
|
|||
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|||
|
|
}
|
|||
|
|
vector<int> path; // 拓扑路径
|
|||
|
|
void topsort() {
|
|||
|
|
queue<int> q;
|
|||
|
|
/*
|
|||
|
|
考虑极限情况：当每一个站点全部停靠的情况下，相当于左侧集合为空（不停靠的没有）
|
|||
|
|
也就没有左侧集合向虚拟点连边这件事，虚拟点的入度为0,此时，虚拟点需要入队列
|
|||
|
|
*/
|
|||
|
|
for (int i = 1; i <= n + m; i++)
|
|||
|
|
if (!in[i]) q.push(i);
|
|||
|
|
|
|||
|
|
while (q.size()) {
|
|||
|
|
int u = q.front();
|
|||
|
|
q.pop();
|
|||
|
|
path.push_back(u);
|
|||
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|||
|
|
int j = e[i];
|
|||
|
|
in[j]--;
|
|||
|
|
if (in[j] == 0) q.push(j);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
int main() {
|
|||
|
|
// 加快读入
|
|||
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|||
|
|
// 建图
|
|||
|
|
memset(h, -1, sizeof h);
|
|||
|
|
cin >> n >> m; // n个火车站,m趟车次
|
|||
|
|
|
|||
|
|
for (int i = 1; i <= m; i++) {
|
|||
|
|
memset(st, 0, sizeof st); // 记录哪些是停靠点
|
|||
|
|
|
|||
|
|
int k;
|
|||
|
|
cin >> k; // 有多少个依靠站
|
|||
|
|
int S = n, T = 1;
|
|||
|
|
for (int j = 1; j <= k; j++) {
|
|||
|
|
int x; // 停靠站编号
|
|||
|
|
cin >> x;
|
|||
|
|
S = min(S, x); // 第一个停靠点
|
|||
|
|
T = max(T, x); // 最后一个停靠点
|
|||
|
|
st[x] = 1; // 记录哪些是停靠点，哪些不是停靠点
|
|||
|
|
}
|
|||
|
|
// 笛卡尔积式建图优化技巧
|
|||
|
|
int u = n + i; // 分配超级源点，虚拟点点号。多条线路，每次一个超级源点，共多建超级源点m个
|
|||
|
|
for (int j = S; j <= T; j++)
|
|||
|
|
if (st[j]) // 如果j不是停靠点
|
|||
|
|
add(u, j, 1), in[j]++; // 虚拟点向右侧集合中每个点连一条长度为1的边
|
|||
|
|
else
|
|||
|
|
add(j, u, 0), in[u]++; // 左侧集合向 虚拟点u 连一条长度为0的边
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// 求拓扑序
|
|||
|
|
topsort();
|
|||
|
|
|
|||
|
|
/*
|
|||
|
|
Q:for (int i = 1; i <= n; i) d[i] = 1;
|
|||
|
|
y总这句话为什么不能这样写呀 for (int i = 1; i <= n + m; i) d[i] = 1;
|
|||
|
|
|
|||
|
|
A:考虑一种边界情况，当全部站点都停靠的时候,此时虚拟节点是入度为0的节点，虚拟节点的等级d应该为0，
|
|||
|
|
因为连向车站的边权已经是1,否则，如果虚拟节点的等级为1，那么连向的车站等级就会是2。
|
|||
|
|
*/
|
|||
|
|
|
|||
|
|
// 递推距离初始化
|
|||
|
|
for (int i = 1; i <= n; i++) d[i] = 1; // n个站点的等级最少是1，而虚拟节点的等级最少是0
|
|||
|
|
// 拓扑路径+递推计算最长路
|
|||
|
|
for (auto u : path) // 枚举拓扑路径的每一个点
|
|||
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|||
|
|
int j = e[i];
|
|||
|
|
d[j] = max(d[j], d[u] + w[i]); // u要求j必须距离自己>=w[i]
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
int res = 0;
|
|||
|
|
for (int i = 1; i <= n; i++) res = max(res, d[i]); // 找出最大值，就是最小等级
|
|||
|
|
printf("%d\n", res);
|
|||
|
|
return 0;
|
|||
|
|
}
|