NOIP2013 车站分级

一条单向的铁路线上,依次有编号为 1, 2, ..., n 的 n 个火车站。每个火车站都有一个级别,最低为 1 级。现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 x,则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。
(注意:起始站和终点站自然也算作事先已知需要停靠的站点)
例如,下表是 5 趟车次的运行情况。其中,前 4 趟车次均满足要求,而第 5 趟车次由于停靠了 3 号火车站(2 级)却未停靠途经的 6 号火车站(亦为 2 级)而不满足要求。

现有 m 趟车次的运行情况(全部满足要求),试推算这 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
  

每个测试点1s。

对于 20%的数据,1 ≤ n, m ≤ 10;
对于 50%的数据,1 ≤ n, m ≤ 100;
对于 100%的数据,1 ≤ n, m ≤ 1000

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 const int MAXN=1000+10;
 6 int n,m,ans=0;
 7 int B[MAXN]={0},R[MAXN]={0},SK[MAXN]={0};
 8 bool A[MAXN]={0},F[MAXN]={0},E[MAXN][MAXN]={0};
 9 
10 int main()
11 {
12     cin>>n>>m;
13     for(int i=1;i<=m;i++)
14     {
15         int s;
16         memset(A,0,sizeof(A));
17         cin>>s;
18         for(int j=1;j<=s;j++)
19         {
20             cin>>B[j];
21             A[B[j]]=1;
22         }
23         for(int j=B[1];j<=B[s];j++)
24             if(!A[j])
25                 for(int k=1;k<=s;k++)
26                     if(!E[j][B[k]])
27                     {
28                         E[j][B[k]]=1;
29                         R[B[k]]++;
30                     }
31     }
32     int top;
33     while(1)
34     {
35         top=0;
36         for(int i=1;i<=n;i++)
37             if(!R[i]&&!F[i])
38             {
39                 SK[++top]=i;
40                 F[i]=1;
41             }
42         if(top==0)break;
43         for(int i=1;i<=top;i++)
44             for(int j=1;j<=n;j++)
45                 if(E[SK[i]][j])
46                 {
47                     E[SK[i]][j]=0;
48                     R[j]--;
49                 }
50         ans++;
51     }
52     cout<<ans<<endl;
53     return 0;
54 }  

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 
 6 struct Edge
 7 {
 8     int to,next;
 9 }E[1000001];
10 int head[100001],r[100001],s[100001];
11 bool f[100001];
12 int node=0;
13 
14 int n,m,ans;
15 
16 void insert(int u,int v)
17 {
18     E[++node]=(Edge){v,head[u]};
19     head[u]=node;
20     r[v]++;
21 }
22 
23 void topsort()
24 {
25     int top;
26     while(1)
27     {
28         top=0;
29         for(int i=1;i<=n;i++)
30             if(!r[i]&&!f[i])
31                 s[++top]=i,f[i]=1;
32         if(top==0) break;
33         for(int i=1;i<=top;i++)
34             for(int j=head[s[i]];j;j=E[j].next)
35                 r[E[j].to]--;
36         ans++;
37     }
38 }
39 
40 int read()
41 {
42     int x=0,f=1;char ch=getchar();
43     while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
44     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
45     return x*f;
46 }
47 
48 int B[1010];
49 bool A[1010],e[1010][1010];
50 
51 int main()
52 {
53     n=read();m=read();
54     for(int i=1;i<=m;i++)
55     {
56         int s=read();
57         memset(A,0,sizeof(A));
58         for(int j=1;j<=s;j++)
59         {
60             B[j]=read();
61             A[B[j]]=1;
62         }
63         for(int j=B[1];j<=B[s];j++)
64             if(!A[j])
65                 for(int k=1;k<=s;k++)
66                     if(!e[j][B[k]])
67                     {
68                         e[j][B[k]]=1;
69                         insert(j,B[k]);
70                     }
71     }
72     topsort();
73     cout<<ans<<endl;
74     return 0;
75 }