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;
|
||
} |