[NOI2010]航空管制(建反图,拓扑排序,优先队列)

题目链接

洛谷

题意简述

给你一个 DAG,每个点有个值 $k_i$。

第一问:求一个拓扑排序,使每个点出现的位置不超过 $k_i$。

第二问:在满足第一问的拓扑排序中,求每个点分别的最早出现位置。

简要做法

第一眼看到这题,在多少之前 $\rightarrow$ 反过来考虑,因为之前好像做过 PJ 难度的类似题目..

然而第二眼就变成了:拓扑排序裸题!然后愉快地写了个假贪心..

不能随便放过自己的直觉啊..

正解就是建反图,这样一定可以每次选 $k$ 最大的,用优先队列拓扑排序就可以了。

第二问的话,还是建反图,依次考虑每个点,不把当前考虑的点加入优先队列中,直到无法符合要求便是答案。

参考代码

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
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int, int> pii;

const int N = 2010;
const int M = 10010;

void add(int u, int v);

int head[N], nxt[M], to[M], cnt;
int n, m, k[N], ind[N], in[N], stk[N], top;
priority_queue<pii> q;

int main()
{
int i, u, v, x, ans;

scanf("%d%d", &n, &m);

for (i = 1; i <= n; ++i) scanf("%d", k + i);

for (i = 1; i <= m; ++i)
{
scanf("%d%d", &u, &v);
add(v, u);
++ind[u];
}

memcpy(in, ind, sizeof(in));
for (i = 1; i <= n; ++i) if (!in[i]) q.push(pii(k[i], i));

while (!q.empty())
{
u = stk[++top] = q.top().second;
q.pop();
for (i = head[u]; i; i = nxt[i])
{
v = to[i];
if (--in[v] == 0) q.push(pii(k[v], v));
}
}

while (top) printf("%d ",stk[top--]);
puts("");

for (x = 1; x <= n; ++x)
{
ans = n;
memcpy(in, ind, sizeof(in));
for (i = 1; i <= n; ++i) if (!in[i]) q.push(pii(k[i], i));

while (!q.empty())
{
u = q.top().second;
q.pop();
if (u == x) continue;
if (k[u] < ans)
{
while (!q.empty()) q.pop();
break;
}
--ans;
for (i = head[u]; i; i = nxt[i])
{
v = to[i];
if (--in[v] == 0) q.push(pii(k[v], v));
}
}

printf("%d ", ans);
}

return 0;
}

void add(int u, int v)
{
nxt[++cnt] = head[u];
head[u] = cnt;
to[cnt] = v;
}