[BZOJ2109] [Noi2010]Plane 航空管制

题目描述 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

5 5 
4 5 2 5 4 
1 2 
3 2 
5 1 
3 4 
3 1 

样例输出 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;
    
}

总结

正难则反

上一篇:luogu P1447_能量采集 (莫比乌斯反演)


下一篇:BZOJ2007/LG2046 「NOI2010」海拔 平面图最小割转对偶图最短路