假设目前被延误航班共有 $n$ 个，编号为 $1$ 至 $n$ 。机场只有一条起飞跑道，所有的航班需按某个顺序依次起飞（称这个顺序为起飞序列）。定义一个航班的起飞序号为该航班在起飞序列中的位置，即是第几个起飞的航班。
起飞序列还存在两类限制条件：
第一类（最晚起飞时间限制）：编号为 $i$ 的航班起飞序号不得超过 $k_i$ ;
第二类（相对起飞顺序限制）：存在一些相对起飞顺序限制 $(a, b)$ ，表示航班 $a$ 的起飞时间必须早于航班 $b$ ，即航班 $a$ 的起飞序号必须小于航班 $b$ 的起飞序号。
小 $\text{X}$ 思考的第一个问题是，若给定以上两类限制条件，是否可以计算出一个可行的起飞序列。第二个问题则是，在考虑两类限制条件的情况下，如何求出每个航班在所有可行的起飞序列中的最小起飞序号。
链接
Luogu P1954
题解
对于这些限制，我们发现可以转换成一个拓扑序的问题。但是我们发现最晚的起飞时间限制比较难达成，而两向的相对关系则是比较轻松的，所以我们考虑到可以把整个时间轴反向，那么就变成了所有飞机都有一个最早起飞的限制，那么就可以加一个虚边，按时间解锁，这个问题就可以解决了。
对于第二问，我们就相当于把这个飞机，反向之后能压多后就压多后，将拓扑排序里面的队列变为优先队列，就可以了。
复杂度是 $O(n^2 \log{n})$，貌似不是正解，BZOJ可过，Luogu 需开 O2 。
代码
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define inf 0x3f3f3f3f
#define pii pair<int,int>
using namespace std;
const int MAXN = 2100;
int n,m;
int k[MAXN];
vector<int> edge[MAXN];
vector<int> qqq[MAXN];
int ans[MAXN];
priority_queue<pii> q;
int toposort(int w = 0){
// printf("w:%d\n",w);
static int in[MAXN];
memset(in,0,sizeof(in));
while(!q.empty()) q.pop();
for(int x = 1;x<=n;x++){
for(int i = 0;i<edge[x].size();i++){
in[edge[x][i]]++;
}
in[x]++;
}
for(int j = n;j>=1;--j){
for(int i = 0;i<qqq[j].size();i++){
int x = qqq[j][i];
if(--in[x] == 0){
q.push(make_pair((w==x?-inf:k[x]),x));
}
}
int x = q.top().second;q.pop();
if(x == w) return j;
ans[j] = x;
for(int i = 0;i<edge[x].size();i++){
int v = edge[x][i];
if(--in[v] == 0){
q.push(make_pair((w==v?-inf:k[v]),v));
}
}
}
return 0;
}
void init(){
scanf("%d %d",&n,&m);
for(int i = 1;i<=n;i++){
scanf("%d",&k[i]);
qqq[k[i]].push_back(i);
}
int a,b;
for(int i = 1;i<=m;i++){
scanf("%d %d",&a,&b);
edge[b].push_back(a);
}
}
void solve(){
toposort();
for(int i = 1;i<=n;i++)
printf("%d ",ans[i]);
printf("\n");
for(int i = 1;i<=n;i++)
printf("%d ",toposort(i));
printf("\n");
}
int main(){
init();
solve();
return 0;
}
|
