[BZOJ2109] [Noi2010]Plane 航空管制

2024-03-24 19:08:10

题目描述 Description

世博期间，上海的航空客运量大大超过了平时，随之而来的航空管制也频频发生。最近，小X就因为航空管制，连续两次在机场被延误超过了两小时。对此，小X表示很不满意。在这次来烟台的路上，小 X不幸又一次碰上了航空管制。于是小 X开始思考关于航空管制的问题。假设目前被延误航班共有 n个，编号为 1至n。机场只有一条起飞跑道，所有的航班需按某个顺序依次起飞（称这个顺序为起飞序列）。定义一个航班的起飞序号为该航班在起飞序列中的位置，即是第几个起飞的航班。起飞序列还存在两类限制条件：  第一类（最晚起飞时间限制）：编号为 i的航班起飞序号不得超过 ki;  第二类（相对起飞顺序限制）：存在一些相对起飞顺序限制(a, b)，表示航班 a的起飞时间必须早于航班 b，即航班 a的起飞序号必须小于航班 b 的起飞序号。小X 思考的第一个问题是，若给定以上两类限制条件，是否可以计算出一个可行的起飞序列。第二个问题则是，在考虑两类限制条件的情况下，如何求出每个航班在所有可行的起飞序列中的最小起飞序号。

输入描述 Input Description

第一行包含两个正整数 n和m，n表示航班数目，m表示第二类限制条件（相对起飞顺序限制）的数目。第二行包含 n个正整数 k1, k2, „, kn。接下来 m行，每行两个正整数 a和b，表示一对相对起飞顺序限制(a, b)，其中1≤a,b≤n, 表示航班 a必须先于航班 b起飞。

输出描述 Output Description

包含 n个整数 t1, t2, „, tn，其中 ti表示航班i可能的最小起飞序号，相邻两个整数用空格分隔。

样例输入 Sample Input

样例输出 Sample Output

3 4 1 2 1

数据范围及提示 Data Size & Hint

n≤2,000，m≤10,000

之前的一些废话

为什么我还做NOI的题，我没救了
不过反正这个博客没人看，管他呢

题解

第二种限制显然是一个拓扑关系，第一种限制告诉你最晚出发时间
正难则反
考虑反向建图，第二种限制除了边反了没有什么区别，第二种限制变成了最早出发时间。
不考虑任何点的情况下，倒着枚举时间，每次选择k最大的，度数为0的点
考虑点i的情况下，先忽视点i，进行一次拓扑排序(注意每次入队的点不光要保证入度为0，也必须保证在该点最早时间以后)
当某个时刻没有点可以选择时，这时必须选择点i，这就是点i出现的最早时间
用堆来维护即可。
复杂度：O(n^2)

代码

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long LL;
typedef pair<int,int> PII;
#define X first
#define Y second
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int maxn=2010,maxm=10010;
struct Edge
{
    int u,v,next;
    Edge() {}
    Edge(int _1,int _2,int _3):u(_1),v(_2),next(_3) {}
}e[maxm];
int n,m,ce=-1,first[maxn],a[maxn],x,y,s[maxn],top,r[maxn],R[maxn];
priority_queue <PII,vector<PII>,greater<PII> > Q;
void addEdge(int a,int b){e[++ce]=Edge(a,b,first[a]);first[a]=ce;r[b]++;}
int calc(int cur)
{
    int now=1;
    mem(s,0);top=0;while(Q.size())Q.pop();
    for(int i=1;i<=n;i++)R[i]=r[i];
    for(int i=1;i<=n;i++)if(R[i]==0 && i!=cur)Q.push(make_pair(a[i],i));
    while(Q.size() && Q.top().X<=now)
    {
        s[++top]=Q.top().Y;
        Q.pop(); 
        now++;
    }
    while(top)
    {
        int x=s[top--];
        for(int i=first[x];i!=-1;i=e[i].next)
        {
            R[e[i].v]--;
            if(!R[e[i].v] && e[i].v!=cur)Q.push(make_pair(a[e[i].v],e[i].v));
        }
        while(Q.size() && Q.top().X<=now)
        {
            s[++top]=Q.top().Y;
            Q.pop(); 
            now++;
        }
    }
    return now;
}
int main()
{
    mem(first,-1);
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=n-read()+1;
    while(m--)x=read(),y=read(),addEdge(y,x);
    for(int i=1;i<=n;i++)
    {
        if(i>1)putchar(' ');
        printf("%d",n-calc(i)+1);
    }
    putchar('\n');
    return 0;
    
}

总结

正难则反

码农公寓