Luogu P1983 车站分级

YorkWu

June 3, 2019

1178 views

No comments

818 words

OI 题目

[题目链接](https://www.luogu.org/problemnew/show/P1983 "题目链接")

* * *

又是一道比较经典的题，据说有什么线段树优化构造。。。反正我是不懂。 这道题使用topsort（拓扑排序）的思想；

*   简化题意：n个车站，每个车站有一个级别，如果有一趟列车，这趟列车经过$a\_1,a\_2,···,a_s$站，且如果这些站中级别最低的车站的级别为$minx$，那么所有在起点站到终点站之间级别大于等于$minx$的车站都必须停靠。那么m趟列车，给定每趟列车的经过站（车站编号升序给出），求所有车站至少分成多少级。
*   思路：如果从起点站到终点站之间有火车站没有停靠，就说明这个火车站的级别一定小于所有停靠了的火车站，那么就将每个没有停靠的火车站向停靠的火车站连一条边，这样用topsort的思想，可算出最终分成了几层，便是最少的级别数量；
*   例如数据 1 3 5 6停靠 ![1](http://yueyangwu.cn/wp-content/uploads/2019/06/56401.png "1")

代码如下
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    
    int n,m,a[1009],cd[1009],st[1009];
    bool v[1009],top[1009][1009],del[1009];
    
    int main(){
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            memset(v,0,sizeof(v));
            int s;
            cin>>s;
            for(int j=1;j<=s;j++){
                cin>>a[j];
                v[a[j]]=1;
            }
            for(int j=a[1];j<=a[s];j++){
                if(!v[j]){
                    for(int k=1;k<=s;k++){
                        if(top[a[k]][j]) continue;
                        top[a[k]][j]=1;
                        cd[a[k]]++;
                    }
                }
            }
        }
        int r=1,ans=0;
        while(r){
            r=0;
            for(int i=1;i<=n;i++){
                if(cd[i]==0&&!del[i]){
                    st[++r]=i;
                    del[i]=1;
                }
            }
            if(r) ans++;
            for(int i=1;i<=r;i++){
                for(int j=1;j<=n;j++){
                    if(!top[j][st[i]]) continue;
                    top[j][st[i]]=0;
                    cd[j]--;
                }
            }
        }
        cout<<ans;
        return 0;
    }
```

Last modification：March 14, 2020