luogu1983 车站分级

luogu1983 车站分级

​​ 题目描述

一条单向的铁路线上，依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别，最低为 1 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）

例如，下表是 5 趟车次的运行情况。其中，前 4 趟车次均满足要求，而第 5 趟车次由于停靠了 3 号火车站（2 级）却未停靠途经的 6 号火车站（亦为 2 级）而不满足要求。

现有 m 趟车次的运行情况（全部满足要求），试推算这 n 个火车站至少分为几个不同的级别。

输入输出格式

输入格式：

输入文件为 level.in。

第一行包含 2 个正整数 n, m，用一个空格隔开。

第 i + 1 行（1 ≤ i ≤ m）中，首先是一个正整数 si（2 ≤ si ≤ n），表示第 i 趟车次有 si 个停靠站；接下来有 si个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。

输出格式：

输出文件为 level.out。

输出只有一行，包含一个正整数，即 n 个火车站最少划分的级别数。

输入输出样例

输入样例#1：

9 2 4 1 3 5 6 3 3 5 6 输出样例#1：

2 输入样例#2：

9 3 4 1 3 5 6 3 3 5 6 3 1 5 9 输出样例#2：

3 说明

对于 20%的数据，1 ≤ n, m ≤ 10；

对于 50%的数据，1 ≤ n, m ≤ 100；

对于 100%的数据，1 ≤ n, m ≤ 1000。

这题感觉着实没有这么简单

思路很重要

我们得知道他给的数据有一个隐藏条件就是我这个经过的站点里所有没有过的点，都比我停靠的站点小

所以我把所有这样的点，去和我停靠的点作一下连接

我每次做的时候都去寻找入度为0的点，加入队列

if (!map[i][a[j]]) map[i][a[j]]=1,in[a[j]]++; 这句话不可少判断条件，否则入度会平白无故多出许多

每次都拓扑排序，最后答案就是我做了 几次拓扑排序

#include#include#define N 1100inline int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f;}int n,m,a[N],in[N],b[N],s,map[N][N],ans,q[N];bool flag[N];int main(){ freopen("1983.in","r",stdin); n=read();m=read(); for (int owo=1;owo<=m;++owo){ int tmp=read();s++; for (int i=1;i<=tmp;++i) a[i]=read(),b[a[i]]=s; for (int i=a[1];i<=a[tmp];++i){ if (b[i]!=s)for (int j=1;j<=tmp;++j) if (!map[i][a[j]]) map[i][a[j]]=1,in[a[j]]++; } } while (1){ int top=0; for (int i=1;i<=n;++i) if (!in[i]&&!flag[i]) q[++top]=i,flag[i]=true; if (!top) break;ans++; for (int j=1;j<=top;++j) for (int i=1;i<=n;++i)if (map[q[j]][i]) in[i]--,map[q[j]][i]=0; } printf("%d",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。