P1954 [NOI2010] 航空管制 题解

发表于 分类于 本文字数： 399 阅读时长 ≈ 1 分钟

true
航空管制
NOI 2010
省选/NOI-
#9d3dcf
  • Luogu P1954
  • LibreOJ L3760
  • AcWing 979
  • BZOJ #2008

本题的思路与[HNOI2015] 菜肴制作很像。
同样是将约束条件当成单向边建反图之后跑拓扑排序，但是这里还需要考虑最晚起飞时间的限制。
因为我们是倒序枚举的时间，所以最晚起飞时间可以转化为最早起飞时间。
我们可以拿一个桶来存储下每一个最晚起飞时间对应的飞机集合，当我们枚举到这个时间之后，将所有的飞机放入堆里。
当然，因为要求的是可行解，所以这里的堆可以换成队列。

对于最早可能的起飞序号，我们可以对每一个飞机做一遍拓扑排序。
这一次做拓扑排序的时候，我们需要让当前选定的这个飞机尽量在队尾，也就是尽量晚出队。
具体实现方式就是在每一次插入新的队尾的时候，看一看能否将当前这个飞机（也就是队尾的前一个元素）与队尾交换位置。

题目保证有解了，就不需要判定无解的情况了。

代码如下：

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2010, M = 100010;
int n, m;
int h[N], e[M], ne[M], idx;
int deg[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int ans[N], tot;
int tmp[N];
vector<int>v[N];
void solve(int u)
{
    int q[N];
    int hh = 1, tt = 0;
    for(int i = 1; i <= n; i++)tmp[i] = deg[i] + 1;
    for(int t = n; t; t--)
    {
        if(!v[t].empty())
        {
            for(auto j : v[t])
            {
                if(!(--tmp[j]))
                {
                    q[++tt] = j;
                    if(hh < tt && q[tt - 1] == u)swap(q[tt], q[tt - 1]);
                }
            }
        }
        int p = q[hh++];
        if(p == u)
        {
            printf("%d ", t);
            break;
        }
        for(int i = h[p]; ~i; i = ne[i])
        {
            if(!(--tmp[e[i]]))
            {
                q[++tt] = e[i];
                if(hh < tt && q[tt - 1] == u)swap(q[tt], q[tt - 1]);
            }
        }
    }
}
int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        v[x].push_back(i);
    }
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        deg[u]++;
        add(v, u);
    }
    priority_queue<int>q;
    for(int i = 1; i <= n; i++)tmp[i] = deg[i] + 1;
    for(int t = n; t; t--)
    {
        if(!v[t].empty())
        {
            for(auto j : v[t])
            {
                tmp[j]--;
                if(!tmp[j])q.push(j);
            }
        }
        int u = q.top();
        q.pop();
        ans[t] = u;
        for(int i = h[u]; ~i; i = ne[i])
            if(!(--tmp[e[i]]))q.push(e[i]);
    }
    for(int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
    putchar('\n');
    for(int i = 1; i <= n; i++)
        solve(i);
    putchar('\n');
    return 0;
}