自动搬运

查看原文

来自洛谷，原作者为

	SCUT_HYX 竹杖芒鞋轻胜马，谁怕？一蓑烟雨任平生

搬运于2025-08-24 21:32:37，当前版本为作者最后更新于2019-04-12 14:06:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更好的阅读体验：黄毛猫_HYX的博客

推销下我的空间：蒟蒻

拓扑思想

先读读题(没读题的请回

因为火车都要停靠比它高级（大于等于）的车站，所以其它不停的就是比它级别小（小于）的车站，现在求最高等级的车站是几级。

在所有不停的站的级别小于停靠的站的情况下，我们可以做出一张图（A指向B表示A车站级别大于B车站）[用的是样例1] 多了7-9号点太丑了所以就去掉了

最后利用拓扑的思想，一层一层的删点删线，统计下分了多少层，答案就出来了QWQ

什么是拓扑：拓扑排序是对有向无回路图进行排序，以期找到一个线性序列，这个线性序列在生活正可以表示某些事情完成的相应顺序。如果说所求的图有回路的话，则不可能找到这个序列。

#include<iostream>
#include<cstdio>
#include<cstring>
#define ZYS 1005
using namespace std;
int n,m,ans,st[ZYS],s,tuopu[ZYS][ZYS],de[ZYS],tt[ZYS],top;
bool is[ZYS],bo[ZYS];			//用andyzys大佬的名字做数组范围
int main() {
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++) {
        memset(is,0,sizeof(is));//is表示是否是停靠站
        scanf("%d",&s);
        for(int j=1;j<=s;j++)
            scanf("%d",&st[j]),is[st[j]]=true;
        for(int j=st[1];j<=st[s];j++)
            if(!is[j])			//枚举站点，若不是已停靠的就小于所有停靠站的等级
                for(int k=1;k<=s;k++)	//枚举已停靠站点
                    if(!tuopu[j][st[k]]) tuopu[j][st[k]]=1,de[st[k]]++;//tuopu[i][j]表示j>i的级别，如上
    }
    
    do{
        top=0;
        for(int i=1;i<=n;i++)
            if(de[i]==0&&!bo[i]) {
                tt[++top]=i,bo[i]=true;//开始将出度为0的点删掉
            }
        for(int i=1;i<=top;i++)
            for(int j=1;j<=n;j++)
                if(tuopu[tt[i]][j]) tuopu[tt[i]][j]=0,de[j]--;//去边去点
        ans++;
    } while(top);
    printf("%d",ans-1);//最后一次什么点都没有会多算一次（自行理解）
    return 0;
}

萌新第一篇题解，不喜勿喷小窗私聊