抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

NOI2010 航空管制

This is a picture without description

pufanyi

题解

发布于：Feb 17, 2019

成功抢到 luogu 最劣解 +bzoj最劣解（至少我提交的时候是这样）……

题意是给你一张拓扑图，求出一个拓扑序使得第 ii 个点在第 kik_i 个位置之前。先构造一组解，然后输出每个点可以到的最小的位置。

构造一组解很简单，建个反图之后按 kik_i 为关键字排序一下，从小到大一个一个遍历即可。因为如果 kik_i 小的航班都没有开出，开 kik_i 大的显然没有意义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline void shan(int now) // 遍历 now 点，但在遍历 now 点时显然先要遍历 now 之前（即反图之后）的点
{
    for(int i = ff[now]; i; i = ee[i].nxt)
    {
        int to = ee[i].to; // ee 是反图中的边
        if(!vis[to])
            shan(to);
    }
    printf("%d ", now);
    vis[now] = true;
}

int main()
{
    for(int i = 1; i <= n; ++i)
        kkk[i] = mp(k[i], i); // #define mp make_pair
    sort(kkk + 1, kkk + n + 1);
    for(int i = 1; i <= n; ++i)
        if(!vis[kkk[i].second])
            shan(kkk[i].second);
}

然后我们发现如果给出的 kk 序列无解，那么输出的序列一定不合法（怎么可能合法？），然后我们发现可以二分。

复杂度？O(nmlog⁡n)\mathcal{O}(nm\log n)……显然 T，T 了 4 个点。

然后开始 O(松)\mathcal{O}(\text{松}) 卡常。

然后发现它过了。

虽然我卡了一年……

下面是卡完的代码：

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
// luogu-judger-enable-o2 开 O2 还是最劣解……
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 2005;
const int maxm = 10005;

int n, m;

// 快读快输显然得加

inline char gc()
{
    static char sxd[1 << 16], *sss = sxd, *ttt = sxd;
    return (sss == ttt) && (ttt = (sss = sxd) + fread(sxd, 1, 1 << 16, stdin), sss == ttt) ? EOF : *sss++;
}

#define dd c = gc()
inline int read(int &x)
{
    char dd;
    x = 0;
    bool f = false;
    for(; !isdigit(c); dd)
    {
        if(c == '-')
            f = true;
        if(c == EOF)
            return -1;
    }
    for(; isdigit(c); dd)
        x = (x << 1) + (x << 3) + (c ^ 48);
    if(f)
        x = -x;
    return 1;
}
#undef dd

inline void write(register int x)
{
    int c[10];
    *c = 0;
    while(x)
    {
        c[++(*c)] = x % 10;
        x /= 10;
    }
    if(!(*c))
        x = 1;
    while(*c)
        putchar(c[(*c)--] | 48);
    putchar(' ');
}

struct pii // 并不知道手打 pair 会不会快一点
{
    int first, second;
    inline bool operator < (const pii& other) const
    {
        return this->first < other.first;
    }
};

pii kkk[maxn];

struct EDGE
{
    int to, nxt;
} ee[maxm]; // 注意是反图的边，原图的边似乎不用建

int du[maxn];
int first[maxn];
int ff[maxn];
int dz[maxn];

inline void add_edge(register int from, register int to)
{
    static int cnt = 0;
    ee[++cnt].nxt = ff[to];
    ff[to] = cnt;
    ee[cnt].to = from;
}

int k[maxn];
int top;
int vis[maxn];

inline void shan(register int now) // 回答第一个问题 
{
    for(register int i = ff[now]; i; i = ee[i].nxt)
        if(!vis[ee[i].to])
            shan(ee[i].to);
    write(now);
    dz[now] = ++top; // 记录一下每个点至少可以在那个时刻被遍历，这样缩小的二分的范围 
    vis[now] = true;
}

pii kx[maxn];
bool viss[maxn];
int X, KK;

inline bool shann(register int now)
{
    for(register int i = ff[now]; i; i = ee[i].nxt)
        if(!viss[ee[i].to])
            if(!shann(ee[i].to))
                return false;
    if(++top > ((now != X) ? k[now] : KK)) // 直接边跑边判断，常数应该会小一点 
        return false;
    return viss[now] = true;
}

inline bool pan(register int x, register int kk)
{
    KK = kk;
    register int now = 0;
    for(register int i = 1; i <= n; ++i)
    {
        kx[i] = kkk[i];
        if(kx[i].second == x)
        {
            kx[i].first = kk;
            now = i;
        }
    }
    pii T;
    // 本来下面一段只是一句 sort，但那个常数是在太大了，只能插排
    while(now > 1 && kx[now].first < kx[now - 1].first) 
    {
        T = kx[now];
        kx[now] = kx[now - 1];
        kx[now - 1] = T;
        now--;
    }
    while(now <= n && kx[now].first > kx[now + 1].first)
    {
        T = kx[now];
        kx[now] = kx[now + 1];
        kx[now + 1] = T;
        now++;
    }
    memset(viss, 0, sizeof(viss));
    top = 0;
    for(register int i = 1; i <= n; ++i)
        if(!viss[kx[i].second])
            if(!shann(kx[i].second))
                return false;
    return true;
}

inline int solve(const register int x)
{
    X = x;
    register int l = 1, r = dz[x], mid; // 二分，r 直接就是上面的 dz 了，即第一个问题 x 在那个位置 
    while(l < r)
    {
        mid = (l + r) >> 1;
        if(!pan(x, mid))
            l = mid + 1;
        else
            r = mid;
    }
    return r;
}

int main()
{
    read(n), read(m);
    for(register int i = 1; i <= n; ++i)
    {
        read(k[i]);
        kkk[i].first = k[i];
        kkk[i].second = i;
    }
    sort(kkk + 1, kkk + n + 1);
    int f, t;
    for(register int i = 1; i <= m; ++i)
    {
        read(f), read(t);
        add_edge(f, t);
    }
    for(register int i = 1; i <= n; ++i)
        if(!vis[kkk[i].second])
            shan(kkk[i].second);
    puts("");
    for(register int i = 1; i <= n; ++i)
        write(solve(i));
    return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://pufanyi.github.io/oi-blog/%E8%88%AA%E7%A9%BA%E7%AE%A1%E5%88%B6/

更新于：Jul 2, 2023

二分

卡常

评论