洛谷P1983-车站分级 题解

题目链接：https://www.luogu.com.cn/problem/P1983 思路来源：https://www.luogu.com.cn/blog/WT666-666/solution-p1983 虽然这位dalao的题解里留了不少坑（幸好我没抄），但是他的思路给了我很大启发。

解法

在完成输入后，我们可以掌握某辆车停靠和不停靠的车站。由于车站最低级别为1，所以说要把初始级别设为1，这样之后我们算出来车站的最高级别就会是车站分出来的级别。

那么怎么来推算每个车站的级别呢？ 假设停靠的站点为1，不停靠的站点为0，当一辆车的情况是这样的时候：1 0 0 0 1 那么外面两个车站的等级显然是高于中间三个的，否则的话就全都要停靠了。 所以说我们就可以从不停靠的车站入手，将停靠的车站的等级改为不停靠的车站的最高等级+1，使其符合条件。

现在你可以先试着自己写下代码了，如果有问题再往下看。

代码（含注释）

#include <iostream>
#include <cstdio>
using namespace std;
int lv[1005],tot[1005],train[1005][1005],stop[1005][1005];//车站的级别 某一辆车停靠的站点数 某辆车的某个站点的编号 某辆车是否停靠某个站点
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) lv[i]=1;//每个车站的最低等级为1
    for(int i=0;i<m;i++){
        int s;
        scanf("%d",&s);
        tot[i]=s;
        for(int j=0;j<s;j++){
            scanf("%d",&train[i][j]);
            stop[i][train[i][j]]=1;
        }
    }
    bool finish=false;
    while(finish==false){
        //cout<<"ok"<<endl;
        finish=true;
        for(int i=0;i<m;i++){
            //cout<<"ok2"<<endl;
            int _max=-1;
            for(int j=train[i][0];j<=train[i][tot[i]-1];j++){
                //cout<<"ok3"<<endl;
                if(stop[i][j]==0) _max=max(_max,lv[j]);//找出不停靠的车站的最大级别
            }
            for(int j=0;j<tot[i];j++){//题目中提到：如果这趟车次停靠了火车站x，
                if(lv[train[i][j]]<=_max){//则始发站、终点站之间所有级别大于等于火车站x的都必须停靠。
                    lv[train[i][j]]=_max+1,finish=false;//所以反过来，如果某个站停靠了，那么它至少也要比没停靠的站中的最大值大。
                    //cout<<"lv changed"<<" "<<_max<<endl;
                }//当有一个站被修改了 就证明这个过程没完成
            }
            _max+=1;
        }
    }
    int _max=-1;
	for(int i=0;i<n;i++) _max=max(_max,lv[i]);
	printf("%d",_max);
    return 0;
}