题目链接


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

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

代码如下

    #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 14th, 2020 at 08:51 pm