题面请点上面。
首先第一问，我第一想法是把它放到一个小根堆中，然而这是不行的。
正确的思路是，把图反过来建，然后放到一个大根堆里去。
至于原因，感性理解一下，正着贪是有后效性，会陷入到局部最优解，而反着贪则是从终点出发，是正确的。
第二问也不难，我们考虑当前这个点，能不动他就不动，直到不动不行了（此时两种情况，一是堆空了，二是有人起飞时间晚于降落时间），此时就是第二问的答案。
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cstdlib> #include<string> #include<cmath> #include<queue> #define SIZE 1000005 #define rint register int using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } inline void write(int x) { if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ; } struct node { int id,v; bool operator < (const node &x) const { return x.v>v; } }; int n,m,cnt,in[SIZE],ru[SIZE],ans[SIZE],v[SIZE]; int head[SIZE],nex[SIZE],to[SIZE],total; priority_queue<node> q; inline void link(int x,int y) { to[++total]=y; nex[total]=head[x]; head[x]=total; return ; } inline void solve1() { for(rint i=1;i<=n;++i) in[i]=ru[i]; for(rint i=1;i<=n;++i) if(!in[i]) q.push((node){i,v[i]}); while(q.size()) { int x=q.top().id;q.pop(); ans[++cnt]=x; for(rint i=head[x];i;i=nex[i]) { int y=to[i];--in[y]; if(!in[y]) q.push((node){y,v[y]}); } } } inline int solve2(int k) { while(q.size()) q.pop(); for(rint i=1;i<=n;++i) in[i]=ru[i]; for(rint i=1;i<=n;++i) if(!in[i] && i!=k) q.push((node){i,v[i]}); for(rint c=n;c>=1;--c) { if(!q.size() || q.top().v<c) return c; int x=q.top().id;q.pop(); for(rint i=head[x];i;i=nex[i]) { int y=to[i];--in[y]; if(!in[y] && y!=k) q.push((node){y,v[y]}); } } } int main() { n=read(),m=read(); for(rint i=1;i<=n;++i) v[i]=read(); for(rint i=1;i<=m;++i) { int x=read(),y=read(); link(y,x);++ru[x]; } solve1(); for(rint i=cnt;i>=1;--i) write(ans[i]),cout<<" ";puts(""); for(rint i=1;i<=n;++i) write(solve2(i)),cout<<" "; return 0; }