先后关系，层级关系。
层级关系
若一个问题中存在层级关系，即只能层级低到层级高。
那么我们可以视为其是一种拓扑排序，可以由层级低的向层级高的建边。
题意：一条单向的铁路线上，依次有编号为 1, 2, …, n1,2,…,n的 nn个火车站。每个火车站都有一个级别，最低为 11 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 xx，则始发站、终点站之间所有级别大于等于火车站xx 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）现有 mm 趟车次的运行情况（全部满足要求），试推算这nn 个火车站至少分为几个不同的级别。
思路：很明显的拓扑排序，那么层级低的向层级高的建边即可。最后求出有多少层。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=1e3+11;
ll gra[maxn][maxn],is[maxn],dr[maxn],vis[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
ll ans=0;
ll n,m;cin>>n>>m;
ll st[maxn],top;
for(ll i=1;i<=m;i++){
memset(is,0,sizeof(is));
ll s;cin>>s;
for(ll j=0;j<s;j++){
cin>>st[j];
is[st[j]]=1;
}
for(ll j=st[0];j<=st[s-1];j++){
if(!is[j]){
for(ll k=0;k<s;k++){
if(!gra[j][st[k]]) gra[j][st[k]]=1,dr[st[k]]++;
}
}
}
}
do{
top=0;
for(ll i=1;i<=n;i++) if(dr[i]==0 && !vis[i]) vis[i]=1,st[top++]=i;
for(ll i=0;i<top;i++){
for(ll j=1;j<=n;j++){
if(gra[st[i]][j]){
gra[st[i]][j]=0,dr[j]--;
}
}
}
ans++;
}while(top);
cout<<ans-1<<endl;
return 0;
}
|
维护层级最小或最大
xtu 1250 Bonus
题目描述
要过年了，老板准备发年终奖，老板准备根据员工的平时表现对比发放奖金，最低发888，每档再增加1000块。
由于工作表现记录有点问题，可能存在矛盾的描述，所以，如果无法发放的话，则所有人，每人发888元。
老板把这个任务交给你，希望你帮他算出一共需要给多少奖金，每人需要发多少奖金？
输入
第一行是一个整数K，表示样例的个数。 每个样例的第一行是两个整数n(1≤n≤10000)和m(0≤m≤50000)，分别表示员工的人数以及工作表现记录的数目，员工的编号从1到n。
以后的m行为两个整数a和b(1≤a≠b≤n)，表示员工a的工作表现比b好。
输入数据保证工作表现不会有重复记录。
输出
每个样例先输出一行为奖金总数，然后再输出一行，按员工号的顺序，输出每个员工的奖金数，中间用一个空格隔开。
思路：维护拓扑排序层级最大值，有环则存在矛盾情况
踩坑：维护层级关系时，用d[ v ]=d[ u ]+1，因为维护的是最大值，所以得用队列维护，保证先入先出。而不能用栈。