洛谷P1983 车站分级

@Pelom  October 31, 2019

题意

数据范围:$1 \le n,m \le 1000$

题解

由题意“则始发站、终点站之间所有级别大于等于火车站$x$的都必须停靠”可知未停靠的站级别一定比$x$的级别小
将大小关系转化为图:将车站视为点,由级别小的车站向级别大的车站连边
随后从入度为$0$的点入手,用拓扑排序求出答案

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1000+10;
typedef pair<int,int> p;
queue<p> Q;
int n,m,s;
int a[N];
int ans;
bool vis[N],G[N][N];
int deg[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        memset(vis,0,sizeof(vis));
        scanf("%d",&s);
        for(int j=1;j<=s;j++){
            scanf("%d",&a[j]);
            vis[a[j]]=1;
        }
        for(int j=a[1];j<=a[s];j++)
            if(!vis[j])
                for(int k=1;k<=s;k++)
                    if(!G[j][a[k]]){
                        G[j][a[k]]=1;
                        deg[a[k]]++;
                    }
    }
    for(int i=1;i<=n;i++)
        if(!deg[i])
            Q.push(make_pair(i,1));
    for(;!Q.empty();){
        p u=Q.front();
        Q.pop();
        for(int i=1;i<=n;i++)
            if(G[u.first][i]){
                deg[i]--;
                if(!deg[i]){
                    Q.push(make_pair(i,u.second+1));
                    ans=max(ans,u.second+1);
                }
            }
    }
    printf("%d",ans);
    return 0;
}

添加新评论