P1983 [NOIP2013] 车站分级(拓扑排序)[通俗易懂]

全栈程序员-站长 • 2022年8月8日下午1:36 • 未分类 • 阅读 5

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

原题链接

题目描述
一条单向的铁路线上，依次有编号为 1, 2, …, n1,2,…,n的 nn个火车站。每个火车站都有一个级别，最低为 11 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 xx，则始发站、终点站之间所有级别大于等于火车站xx 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）

例如，下表是55趟车次的运行情况。其中，前44 趟车次均满足要求，而第 55 趟车次由于停靠了 33 号火车站（22 级）却未停靠途经的 66 号火车站（亦为 22 级）而不满足要求。

在这里插入图片描述

现有 mm 趟车次的运行情况（全部满足要求），试推算这nn 个火车站至少分为几个不同的级别。

输入格式

第一行包含 2 个正整数 n, m，用一个空格隔开。
第 i + 1 行(1 ≤ i ≤ m)中，首先是一个正整数 s_i(2 ≤ s_i ≤ n)，表示第i 趟车次有 s_i个停靠站；接下来有s_i个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求

输出格式
一个正整数，即 n 个火车站最少划分的级别数。

输入输出样例

输入

9 2 
4 1 3 5 6 
3 3 5 6

输出

输入

输出

题解
将没经过的火车站等级一定要比经过的火车站等级低，这启发我们用拓扑排序来解决问题。我们可以将没经过的火车站指向经过的火车站，然后拓扑一层一层的删节点，看一共能删几层

#include<bits/stdc++.h>
#include<cmath>
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
#define left(x) x<<1
#define right(x) x<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef struct Node * pnode;
const int N = 1e3 + 10;
const int M = 5e5 + 10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int Mod = 4e8;
int head[N],cnt;
int in[N];
int n,m;
struct Edge{ 
   
    int v,next;
}edge[ M];
bool g[N][N];
void add(int u,int v){ 
   
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
vector<int>q;
vector<int>temp;
int vis[N];
int qq[N],hh = 0,tt = 0;
int topSort(){ 
   
    for(int i = 1;i <= n;i ++)
        if(!in[i])
            qq[tt ++] = i;
// cout<<tt<<endl;
    int res = 0;
    while(hh < tt){ 
   
        res ++;
        temp.clear();
        while(hh < tt){ 
   
            int t = qq[hh ++];
            for(int i = head[t];~i;i = edge[i].next){ 
   
                int ver = edge[i].v;
                if(!(--in[ver]))
                    temp.push_back(ver);
            }
        }
        for(auto &a : temp)
            qq[tt ++] = a;
    }
    return res;
}
int main(){ 
   
    memset(head,-1,sizeof head);
    int k,x;
    cin>>n>>m;
    for(int i = 0;i < m;i ++){ 
   
        cin>>k;
        memset(vis,0,sizeof vis);
        q.clear();
        for(int j = 0;j < k;j ++){ 
   
            cin>>x;
            vis[x] = true;
            q.push_back(x);
        }
        //注意需要从火车站经过的起始站和终止站中选择
        for(int i = q[0];i <= q[q.size() - 1];i ++){ 
   
            if(!vis[i]){ 
   
                for(auto &a : q){ 
   
// cout<<i<<"->"<<a<<endl;
                    if(g[i][a])continue;
                    else g[i][a] = true;
                    add(i,a);
                    in[a] ++;
                }
            }
        }
    }

    int res = topSort();

    cout<<res<<endl;
    return 0;
}