题解 | 车站分级-NOIP2013普及组复赛A题

输入

输出

解析：拓扑排序。
火车停靠站的级别总是高于未停靠站的，类似于拓扑排序里的先后顺序。
假设一列火车的起点站为 s ，终点站为 e ，则途中的所有停靠站向未停靠站连一条边，表示停靠站的级别高于未停靠站，这样处理之后，就得到一个AOV图。
主要的就是拓扑排序记录层次数就是答案，具体实现的话首先构造有向图，期中表示某趟火车从a车站到b车站途中没有停的车站，表示某趟火车从a车站到b车站途中必停的车站，由低构造有向图，
对改图反复执行操作：
1.将所有入度读为零的点入栈。
2.将栈中所有点相连的边去掉，相连的点入度 -1。
（对相连点进行判断，若入度为零，则保存起来。因为下一批入度为零的点必然是与本批入读为零的点项相连的）
执行次数即为答案。

参考代码：

   #include<cstdio>  
    #include<iostream>  
    #include<algorithm>  
    #include<cstring>  
    #include<queue>  
    using namespace std;  
    int sta[1010],map[1010][1010],in[1010];  
    bool vis[1010];  
    int main(){  
        int t,n,m;  
        queue<int>q;  
        cin>>n>>m;   
        for(int i=1;i<=m;i++){  
            memset(vis,0,sizeof(vis));  
            cin>>t;  
            for(int j=1;j<=t;j++){  
                cin>>sta[j];  
                vis[sta[j]]=true;  
            }  
            for(int j=sta[1];j<sta[t];j++){  
                if(!vis[j]){  
                    vis[j]=true;  
                    for(int k=1;k<=t;k++){  
                        if(map[j][sta[k]]==0){//把没有停下的车站连接到停下的  
                            map[j][sta[k]]=1;  
                            in[sta[k]]++;  
                        }  
                    }  
                }  
            }     
        }  
        memset(vis,0,sizeof(vis));  
        int ans=0;  
        while(1){//只要还有数就一直循环  
            for(int i=1;i<=n;i++){  
                if(in[i]==0&&!vis[i]){  
                    q.push(i);  
                    vis[i]=true;  
                }  
            }  
            if(q.empty())break;//一旦都找完了，就跳出  
            while(!q.empty()){    
                for(int i=1;i<=n;i++){  
                    if(map[q.front()][i]==1){  
                        map[q.front()][i]=0;  
                        in[i]--;      
                    }  
                }  
                q.pop();//每找完一个就把找的弹出来  
                 }  
        ans++;  
    }     
    cout<<ans;  
}  

来源：蓝色如烟