LG1983 「NOIP2013」车站分级 拓扑排序

问题描述

LG1983

题解

考虑建立有向边\((a,b)\)，代表\(a\)比\(b\)低级。

于是枚举每一辆车次经过的车站\(x \in [l,r]\)，如果不是车辆停靠的车站，则从\(x\)向每个停靠了的车站连边。

拓扑排序，建立分层图，搞出最大的层数即可。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;



template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-'){
        fh=-1;ch=getchar();
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

const int maxn=1007;
const int maxm=1000007;
int k,a[maxn],ina[maxn];
bool exist[maxn][maxn];
int n,m;
int Head[maxn],Next[maxm],to[maxm],tot=1;

int rd[maxn];

void add(int x,int y){
    to[++tot]=y,Next[tot]=Head[x],Head[x]=tot;
}

int dep[maxn],ans=1;

void toposort(){
    queue<int>q;
    for(int i=1;i<=n;i++){
        if(!rd[i]){
            q.push(i);dep[i]=1;
        }
    }
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=Head[x];i;i=Next[i]){
            int y=to[i];--rd[y];
            if(!rd[y]){
                q.push(y);dep[y]=dep[x]+1;
                ans=max(dep[y],ans);
            }
        }
    }
}

int main(){
    read(n);read(m);
    for(int i=1;i<=m;i++){
        read(k);memset(ina,0,sizeof(ina));
        for(int j=1;j<=k;j++){
            read(a[j]);ina[a[j]]=1;
        }
        for(int j=a[1];j<=a[k];j++){
            if(ina[j]) continue;
            for(int p=1;p<=k;p++){
                if(!exist[j][a[p]]){
                    ++rd[a[p]];add(j,a[p]);
                    exist[j][a[p]]=1;
                }
            }
        }
    }
    toposort();
    printf("%d\n",ans);
    return 0;
}