P1983 车站分级

题目描述

一条单向的铁路线上,依次有编号为 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。

思路我就不多说了,不懂的可以参考楼下,就是建边+拓扑排序

我来解答一下讨论区的疑问

一.8.9.10这三个点莫名RE,那么请开一个map数组,记录两条边之间有没有路径相连,相当于一个访问标记

二.第2、8点TLE ,检查一下你的读入时候的枚举,必须要先枚举开始和结束的所有点,然后满足条件的话再暴力建边

三.还是TLE ,请把你的map数组改成bool类型!!!!!!!!!!!!!!!

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<queue>
 7 using namespace std;
 8 void read(int & n)
 9 {
10     char c='+';int x=0;int flag=0;
11     while(c<'0'||c>'9')
12     {
13         c=getchar();
14         if(c=='-')
15         flag=1;
16     }
17     while(c>='0'&&c<='9')
18     x=x*10+(c-48),c=getchar();
19     flag==1?n=-x:n=x;
20 }
21 const int MAXN=1001;
22 struct node
23 {
24     int u,v,nxt;
25 }edge[1000001];
26 int head[MAXN];
27 int num=1;
28 int n,m,p,gg;
29 int a[MAXN];
30 int vis[MAXN];
31 int rudu[MAXN];
32 int step[MAXN];
33 bool map[MAXN][MAXN];
34 inline void add_edge(int x,int y)
35 {
36     edge[num].u=x;
37     edge[num].v=y;
38     edge[num].nxt=head[x];
39     head[x]=num++;
40 }
41 inline void init()
42 {
43     read(n);read(m);
44     for(int i=1;i<=n;i++)head[i]=-1;
45     for(int i=1;i<=m;i++)
46     {
47         memset(vis,0,sizeof(vis));
48         read(p);
49         for(int i=1;i<=p;i++)
50         {
51             read(a[i]);
52             vis[a[i]]=1;
53         }
54         for(int i=1;i<=p;i++)
55             for(int j=a[1];j<=a[p];j++)
56                 if(vis[j]==0&&map[a[i]][j]==0)
57                 {
58                     add_edge(a[i],j);
59                     map[a[i]][j]=1;
60                     rudu[j]++;        
61                 }
62     }
63 }
64 inline void Topsort()
65 {
66     queue<int>q;
67     for(int i=1;i<=n;i++)
68         if(rudu[i]==0)
69             q.push(i);
70     int ans=0;
71     while(q.size()!=0)
72     {
73         int p=q.front();
74         q.pop();
75         for(int i=head[p];i!=-1;i=edge[i].nxt)
76         {
77             rudu[edge[i].v]--;
78             if(rudu[edge[i].v]==0)
79             {
80                 q.push(edge[i].v);
81                 step[edge[i].v]=step[edge[i].u]+1;
82                 ans=max(ans,step[edge[i].v]);
83             }
84         }
85     }
86     printf("%d",ans+1);
87 }
88 int main()
89 {
90     init();
91     Topsort();
92     return 0;
93 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • cf1000F. One Occurrence(线段树 set)

    首先把询问离线,预处理每个数的\(pre, nxt\),同时线段树维护\(pre\)(下标是\(pre\),值是\(i\)),同时维护一下最大值

    attack
  • P2658 汽车拉力比赛

    题目描述 博艾市将要举行一场汽车拉力比赛。 赛场凹凸不平,所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500),每个单元格的海拔范围在0到10^9之...

    attack
  • P1629 邮递员送信

    题目描述 有一个邮递员要送东西,邮局在节点1.他总共要送N-1样东西,其目的地分别是2~N。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有M条道路,...

    attack
  • 395. Longest Substring with At Least K Repeating Characters

    这是一个经典的分治法解决的问题,关键在于我们如何将这个问题分解为更小的子问题。反过来想,这个子字符串一定不包含什么元素呢?当一个元素出现的总次数小于k,那么该元...

    眯眯眼的猫头鹰
  • cf1000F. One Occurrence(线段树 set)

    首先把询问离线,预处理每个数的\(pre, nxt\),同时线段树维护\(pre\)(下标是\(pre\),值是\(i\)),同时维护一下最大值

    attack
  • POJ-1088 滑雪 (记忆化搜索,dp)

    滑雪 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 86318 ...

    ShenduCC
  • cf547D. Mike and Fish(欧拉回路)

    attack
  • P2419 [USACO08JAN]牛大赛Cow Contest

    题目背景 [Usaco2008 Jan] 题目描述 N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are ...

    attack
  • P1418 选点问题

    题目描述 给出n个点,m条边,每个点能控制与其相连的所有的边,要求选出一些点,使得这些点能控制所有的边,并且点数最少。同时,任意一条边不能被两个点控制 输入输出...

    attack
  • P2658 汽车拉力比赛

    题目描述 博艾市将要举行一场汽车拉力比赛。 赛场凹凸不平,所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500),每个单元格的海拔范围在0到10^9之...

    attack

扫码关注云+社区

领取腾讯云代金券