洛谷P1983车站分级题解

题目

这个题非常毒瘤,只要还是体现在其思维难度上,因为要停留的车站的等级一定要大于不停留的车站的等级,因此我们可以从不停留的车站向停留的车站进行连边,然后从入度为0的点即不停留的点全都入队,然后拓扑排序即可

代码

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int in[199091], lin[100100], dep[100100], data[100100], vis[10001], cnt, n, m, ans, b[4010][4010];
struct edge {
int to, nex;
}e[1000100];
inline void add(int a, int b)
{
e[++cnt].to = b;
e[cnt].nex = lin[a];
lin[a] = cnt;
in[b]++;
}
inline void topu()
{
queue <int> q;
for (int i = 1; i <= n; i++)
if (!in[i])
q.push(i), dep[i] = 1;
while (!q.empty())
{
int cur = q.front();
q.pop();
for (int i = lin[cur]; i; i = e[i].nex)
{
int to = e[i].to;
dep[to] = dep[cur] + 1;
ans = max(ans, dep[to]);
in[to]--;
if (!in[to])
q.push(to);
}
}
printf("%d", ans);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int a;
memset(data, 0, sizeof(data));
memset(vis, 0, sizeof(vis));
scanf("%d", &a);
for (int j = 1; j <= a; j++)
scanf("%d", &data[j]), vis[data[j]] = 1;
for (int k = data[1] + 1; k <= data[a]; k++)
if (!vis[k])
for (int l = 1; l <= a; l++)
if (!b[k][data[l]])
b[k][data[l]] = 1, add(k, data[l]);
}
topu();
return 0;
}
上一篇:(2)Python3笔记 数据类型之"组"(序列) 与 集合


下一篇:Python Windows下打包成exe文件