luogu1983[NOIP2013pjT4] 車站分級(拓撲排序)

題目描述

一條單向的鐵路線上，依次有編号為 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。

1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const int MAX1=1005,MAX2=MAX1*MAX1;
 5 int n,m,ans,du[MAX1],a[MAX1],deep[MAX1],f[MAX1][MAX1];
 6 int tot,head[MAX1],adj[MAX2<<1],next[MAX2<<1];
 7 inline int read(){
 8     int an=0,x=1;char c=getchar();
 9     while (c<'0' || c>'9') {if (c=='-') x=-1;c=getchar();}
10     while (c>='0' && c<='9') {an=(an<<3)+(an<<1)+c-'0';c=getchar();}
11     return an*x;
12 }
13 void addedge(int u,int v){
14     tot++,du[v]++;f[u][v]=1,adj[tot]=v,next[tot]=head[u],head[u]=tot;
15 }
16 void topsort(){
17     int i,j;
18     queue <int> q;
19     for (i=1;i<=n;i++) if (!du[i]) deep[i]=1,q.push(i);
20     while (!q.empty()){
21         int u=q.front();q.pop();
22         for (i=head[u];i;i=next[i]){
23             deep[adj[i]]=max(deep[adj[i]],deep[u]+1);
24             du[adj[i]]--;
25             if (!du[adj[i]]) q.push(adj[i]);
26         }
27     }
28 }
29 int main(){
30     freopen ("level.in","r",stdin);freopen ("level.out","w",stdout);
31     int i,j,k;bool vis[MAX1];
32     n=read(),m=read();
33     for (i=1;i<=m;i++){
34         a[0]=read();
35         memset(vis,false,sizeof(vis));
36         for (j=1;j<=a[0];j++) a[j]=read(),vis[a[j]]=true;
37         for (j=1;j<=a[0];j++)
38             for (k=a[1]+1;k<a[a[0]];k++)
39                 if (!vis[k] && !f[a[j]][k])
40                     addedge(a[j],k);
41     }
42     topsort();
43     for (i=1;i<=n;i++) ans=max(ans,deep[i]);
44     printf("%d",ans);
45     return 0;
46