「NOI2010」航空管制

发布于 2018-11-21  319 次阅读


题目描述

题目链接
有 $n$ 个航班依次起飞,一个时刻只能有一个飞机起飞,并且有 $m$ 个限制:
1. 第一种限制,第 $i$ 个飞机必须在 $c_i$ 的时刻前起飞。
2. 第二种限制,第 $i$ 个飞机必须在第 $j$ 个飞机之前起飞。
询问:
1. 一个可行的起飞方案。
2. 每个飞机最早的起飞时间。
$ n \leq 2 \times 10^3, m \leq 10^4$

题解

首先这是一道十分套路的反图拓扑排序。
举例:如果想求出一张有向图中标号 $x$ 的节点最靠前的拓扑序,怎么求?
显然不能开个堆直接跑,这是字典序最小的不保证 $x$ 在最前面,但是我们如果建出反图在反图跑最大字典序的话,就一定能让 $x$ 尽量朝后,答案就是把这个反图拓扑序列 reverse 一下。
那么对于第一问,我们按照第二种限制建出反图,显然第一种的每个限制就变成了每一个航班在拓扑序中的位置 $ pos >n-c_i $,然后按照第一种限制将节点扔到小根堆里跑一边拓扑排序最后 reverse 一下就可以了。
对于第二问,我们考虑在反图中遍历到 $x$ 节点的时候,一直等到有一个约束失效的时候在让 $x$ 入队,这样就能保证 $x$ 尽量靠后(reverse 后尽量靠前)。
时间复杂度瓶颈在于第二种询问,为 $O(n^2)$

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define Re register
#define LL long long
#define CLR(a,b) memset(a,b,sizeof(a))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2000+5;
const int MAXM = 10000+5;

struct Node{
    struct Edge *firstEdge;
    int du,num;
}node[MAXN];

struct Edge{
    Node *s,*t;
    Edge *next;
}pool[MAXM],*frog = pool;

Edge *New(Node *s,Node *t){
    t->du++;
    Edge *ret = ++frog;
    ret->s = s;ret->t = t;
    ret->next = s->firstEdge;
    return ret;
}

inline void add(int u,int v){
    node[u].firstEdge = New(&node[u],&node[v]);
}

int N,M;
int d[MAXN];
#define P std::pair
#define MP std::make_pair
std::priority_queue,std::greater

> q; std::vector ans; inline void topsort(){ FOR(i,1,N) if(!node[i].du) q.push(MP(N-d[i],&node[i])); while(!q.empty()){ Node *v = q.top().second;q.pop(); ans.push_back(v->num); //DEBUG(v->num);DEBUG(v->firstEdge); for(Edge *e = v->firstEdge;e;e = e->next){ if(!--e->t->du) q.push(MP(N-d[e->t->num],e->t)); } } ROF(i,N-1,0) printf("%d ",ans[i]);puts(""); } int t[MAXN]; inline int calc(int x){ int cnt = 0; while(!q.empty()) q.pop(); // q.clear(); FOR(i,1,N) node[i].du = t[i]; FOR(i,1,N) if(!node[i].du) q.push(MP(N-d[i],&node[i])); while(!q.empty()){ Node *v = q.top().second;q.pop(); if(v == &node[x]) continue; if(N-cnt > d[v->num]) return N - cnt; cnt++; for(Edge *e = v->firstEdge;e;e = e->next){ if(!--e->t->du) q.push(MP(N-d[e->t->num],e->t)); } } return N - cnt; } int main(){ read(N);read(M); FOR(i,1,N) read(d[i]),node[i].num = i; FOR(i,1,M){ int u,v;read(u);read(v); add(v,u); } FOR(i,1,N) t[i] = node[i].du; topsort(); FOR(i,1,N) printf("%d ",calc(i));puts(""); return 0; }


一个OIer。