P1983 [NOIP2013 普及组] 车站分级

题目

链接

https://www.luogu.com.cn/problem/P1983

题意

每个火车站都有一个级别，每一趟火车如果停靠火车站x则始发站、终点站之间所有级别>=h火车站x的都必须停靠，问有m趟火车至少划分出多少级别

思路

拓扑排序

1. 只要是涉及到级别、优先级，要干什么，就必须先干什么的这类型的题，我们就要考虑到拓扑排序；此题状态转移方程和1352：【例4-13】奖金——拓扑排序一样，并且同样也是拓扑排序；

2. 火车没有停的车站，一定比上面的停过的车站等级小，所以 没经过的停车站 指向 经过的停车站；所以vis标记下经过的停车站，存进stop，然后后续建边用；

3. f[i]的含义就是第i个车站的等级，首先f初始化为1，表示最少都是一个级别，状态转移方程和奖金一样，f[v] = max(f[v], f[u] + 1);前面的结点指向后面结点，那说明就不在一层，尽量少分为几个不同的级别，所以+1，前后相差一个级别即可（奖金那个尽可能少发钱，那他的上司比下一级多1元即可，和这个题的状态转移方程一样）；

4. 为了防止重边，用一个visEdge去标记已经建立过的边，RE的都是因为没有处理重边造成的；

代码

C++

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 1e4+15;
vector<int>g[N];
queue<int>q;
int f[N];
int n,m;
int in[N],a[N];
bool st[N][N];
bool is[N];
int ans;
void topsort(){
    for(int i=1;i<=n;i++){
        if(!in[i]){
            q.push(i);
            f[i]=1;
        }
    }   
    while(!q.empty()){
        int tt = q.front();q.pop();//队头出队
        for(auto it:g[tt]){
            // cout << " id=="<<it<<" f=="<<f[it]<<"\n";
            in[it]--;//删除u->v这条边
            if(!in[it])q.push(it);
            f[it]=f[tt]+1;//前后差一级即可
            ans = max(f[it],ans);
        }
    }
}
signed main(){
	cin >> n >> m;
	for(int i=1;i<=m;i++){
        memset(a,0,sizeof(a));
        memset(is,0,sizeof(is));
		int nn;
		cin >> nn;
		for(int j=1;j<=nn;j++){
            cin >> a[j];
            is[a[j]]=1;//将火车停靠的车站标记1
		}
//没有停的车站，一定比上面经过停车站的车站等级小，所以 没经过的停车站 指向 经过的停车站
        for(int j=a[1] +1 ;j<=a[nn];j++){
            if(!is[j])//将火车停靠的车站标记1
                for(int p=1;p<=nn;p++){//经过的停车站
                    if(!st[j][a[p]]){//经过的停车站
                        in[a[p]]++;//入度++
                        g[j].pb(a[p]);
                        st[j][a[p]]=1;
                    }
                }
        }
	}
    topsort();
    cout << ans << "\n";
}   

31/10/2023 13:34