这一题是来自YBTOJ的题目，题中运用到了拓扑排序和二叉堆的使用。

题目描述：

  目前机场有 趟被延误航班，编号为 至 。机场只有一条起飞跑道，所有的航班需按某个顺序依次起飞（称这个顺序为起飞序列）。定义一个航班的起飞时间为该航班在起飞序列中的位置，即是第几个起飞的航班。

  起飞序列必须满足以下条件：

  限制一：编号为 的航班起飞时间不得超过 。
  限制二：存在一些相对起飞顺序限制 ，表示航班 必须在航班 之前起飞。
有两个问题：

  1.在考虑两类限制条件的情况下，是否可以计算出一个可行的起飞序列。
  2.在考虑两类限制条件的情况下，如何求出每个航班在所有可行的起飞序列中的最小起飞时间。

输入输出格式：

样例输入输出

数据范围：

  关于这一题，可以分成两个问题。
  一个是怎么求出一个可行的起飞序列。
  解决这个问题，需要一点点转换能力，这一题我就以样例一为例子，首先，这个样例里，要求三号飞机在一号二号四号飞机前起飞，一号飞机必须在二号飞机前起飞，五号飞机必须在一号飞机前起飞，那么很容易注意到，当一架飞机，没有被任何一架飞机强制要求飞在后面的时候，这台飞机是可以飞在第一个时间点的，比如三号，也比如五号。
  如果顺着这个思路写下去，那我们统计一下某一架飞机被几架飞机强制要求飞在后面就好了。那么就能写出如下对应数组

  如果单纯照着这个数组写，将值从小到大排序一遍然后输出，就会把三号飞机安排在一号位，五号飞机安排到二号位，因为它们前面可以没有飞机，那放前面肯定是最优的，然后四号飞机放三号位，一号飞机放四号位，二号飞机放五号位。
  如果是这样的话，就会很容易思考到一个问题，这个样例里的确是要求一号飞机飞在二号飞机前面，但是如果反过来，那么上面举出的例子顺序就错误了啊，这就让我们深思了。该怎么确认这个飞机前面该飞的飞机已经飞了呢？
  如果你有很强的抽象和联想能力，我想你已经想到了解决办法。那就是，将关系转化成图，用拓扑排序来解决这个问题。
  为什么能够想到呢，因为上面那张图仔细观察，你会发现，这不就是将边反向之后（如题目中的第一对关系是1 2代表1在2之前起飞，正向边是1连接2，反向边是2连接1，这样，这个点的入度也就代表它前面必须起飞的飞机数量）的入度吗，只要我每次删除一个点，把他加入到答案里，然后把连着的点的入度都减一，那么这个点的入度为零的时候，也就是它前面的飞机都飞完的时候，它就可以起飞了，非常的玄妙。
  代码实现方面，建立一个从小到大排序的优先队列也就是小根堆，将时间反转，也就是原本是最晚在二号位，反转后为N-二 号位，这部分，很遗憾我未能吃透，如果你有想法，可以在评论区里交流一下。

以下是这部分的核心代码，在文章结尾我会把完整代码写上

int cnt=0;
	while(!q.empty())
	{
		int now=q.top().d;
		q.pop();
		first[++cnt]=now;
		
		for (int i=head[now];i;i=edge[i].next)
		{
			int v=edge[i].v;
			temp[v]--;
			if(temp[v]==0)
			{
				q.push((node){n-k[v],v});
			}
		}
	}
	
	for (int i=n;i>=1;i--)
	{
		cout<<first[i]<<" ";
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

  另一个问题是怎么求出每个点的最小起飞时间。
  延续第一问的思路，饱经数学摧残的你应该知道，如果一个大题分成了两个问，那么解决第一问的思路或者答案，肯定是对第二问有用的，我们继续建立反向边，这样可以让这个飞机尽可能的早出现，然后我们遍历一遍飞机，每次都跑一遍拓扑，但循环到第i个时候，如果碰见了第i个，就直接跳过，抛弃这个飞机，那么，当其他飞机无法在某个时间起飞的时候，这个时间就是第i个航班最少的时间。

#include
using namespace std;
struct EDGE
{
	int v;
	int next;
}edge[10086];
int head[10086],num=0;
int n,m;
inline void add(int u,int v)
{
	edge[++num].v=v;
	edge[num].next=head[u];
	head[u]=num;
}
struct node
{
	int t;
	int d;
	bool operator < (const node&a)
	const{
			if(t==a.t)return d>a.d;
			return t>a.t;
	}//因为优先队列默认从大到小，比较函数如果从大到小，那优先队列就是从小到大 
};
priority_queue<node> q;
int ru[10086],k[10086];
int temp[10086];
int first[10086];

inline int ans(int x)
{
	int cnt=0;
	while(!q.empty())
	{
		q.pop();
	}
	for (int i=1;i<=n;i++)
	{
		temp[i]=ru[i];
		if(temp[i]==0)q.push((node){n-k[i],i});
	}
	
	while(!q.empty())
	{
		int now=q.top().d;
		q.pop();
		if(now==x)continue;
		if(n-cnt>k[now])
		{
			return n-cnt;
		}
		cnt++;
		for (int i=head[now];i;i=edge[i].next)
		{
			int v=edge[i].v;
			temp[v]--;
			if(temp[v]==0)
			{
				q.push((node){n-k[v],v});
			}
		}
	}
	return n-cnt;
}

int main()
{
	cin>>n>>m;
	
	for (int i=1;i<=n;i++)
	{
		cin>>k[i];
	}
	int u,v;
	for (int i=1;i<=m;i++)
	{
		cin>>u>>v;
		add(v,u);
		ru[u]++;
	}
	for (int i=1;i<=n;i++)
	{
		temp[i]=ru[i];
		if(temp[i]==0)
		{
			q.push((node){n-k[i],i});
		}
	}
	
	int cnt=0;
	while(!q.empty())
	{
		int now=q.top().d;
		q.pop();
		first[++cnt]=now;
		
		for (int i=head[now];i;i=edge[i].next)
		{
			int v=edge[i].v;
			temp[v]--;
			if(temp[v]==0)
			{
				q.push((node){n-k[v],v});
			}
		}
	}
	
	for (int i=n;i>=1;i--)
	{
		cout<<first[i]<<" ";
	}
	cout<<endl;
	for (int i=1;i<=n;i++)
	{
		cout<<ans(i)<<" ";
	}
}
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

总结

  这一题今天能够钻研的时间比较少，还没有完全吃透，但是收获还是有的。