noi 2010 航空管制贪心

【问题描述】

世博期间，上海的航空客运量大大超过了平时，随之而来的航空管制也频频发生。最近，小X就因为航空管制，连续两次在机场被延误超过了两小时。对此，小X表示很不满意。

在这次来烟台的路上，小X不幸又一次碰上了航空管制。于是小X开始思考关于航空管制的问题。

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

起飞序列还存在两类限制条件：

第一类（最晚起飞时间限制）：编号为i的航班起飞序号不得超过k_i;
第二类（相对起飞顺序限制）：存在一些相对起飞顺序限制(a, b)，表示航班a的起飞时间必须早于航班b，即航班a的起飞序号必须小于航班b的起飞序号。

小X思考的第一个问题是，若给定以上两类限制条件，是否可以计算出一个可行的起飞序列。第二个问题则是，在考虑两类限制条件的情况下，如何求出每个航班在所有可行的起飞序列中的最小起飞序号。

思路：核心是求出每个点最晚出发时间

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstring>
  5 #include<algorithm>
  6 using namespace std;
  7 #define MAXN 2001
  8 #define MAXM 100001
  9 #define INF 987654321
 10 struct node
 11 {
 12     int num;
 13     node *next;
 14 };
 15 node *graph[MAXN],memo[MAXM];
 16 int w[MAXN],finish[MAXN];
 17 bool use[MAXN];
 18 bool map[MAXN][MAXN];
 19 int n,m,top=0,label=0;
 20 pair<int,int> sorted[MAXN];
 21 void add(int x,int y)
 22 {
 23     node *p=&memo[top++];
 24     p->num=y; p->next=graph[x]; graph[x]=p;
 25 }
 26 void topo(int x)
 27 {
 28     use[x]=1;
 29     for(node *p=graph[x];p;p=p->next)
 30     if(!use[p->num])
 31         topo(p->num);
 32     finish[++label]=x;
 33 }
 34 void dfs(int x,int u)
 35 {
 36     use[u]=1;
 37     map[x][u]=1;
 38     for(node *p=graph[u];p;p=p->next)
 39     if(use[p->num]==0)
 40         dfs(x,p->num);
 41 }
 42 void make()
 43 {
 44     int i;
 45     for(i=n;i>0;i--)
 46     {
 47         int u=finish[i];
 48         for(node *p=graph[u];p;p=p->next)
 49             w[p->num]=min(w[p->num],w[u]-1);
 50     }
 51     for(i=1;i<=n;i++)
 52         sorted[i]=make_pair(w[i],i);
 53     sort(sorted+1,sorted+n+1);
 54     for(i=1;i<n;i++)
 55         printf("%d ",sorted[i].second);
 56     printf("%d\n",sorted[n].second);
 57 }
 58 
 59 void solve(int x)
 60 {
 61     int i,j=n;
 62     for(i=n;i>0;i--)
 63     {
 64         int u=sorted[i].second;
 65         if(map[x][u]==0&&w[u]>=j)
 66             j--;
 67         else if(w[u]<j)
 68             break;
 69     }
 70     printf("%d ",j);
 71 }
 72 int main()
 73 {
 74     //freopen("plane10.in","r",stdin);
 75     //freopen("plane.out","w",stdout);
 76     memset(map,0,sizeof(map));
 77     memset(use,0,sizeof(use));
 78     memset(graph,0,sizeof(graph));
 79     scanf("%d%d",&n,&m);
 80     int i;
 81     int x,y;
 82     for(i=1;i<=n;i++)
 83         scanf("%d",w+i);
 84     for(i=1;i<=m;i++)
 85     {
 86         scanf("%d%d",&x,&y);
 87         add(y,x);
 88     }
 89     for(i=1;i<=n;i++)
 90         if(use[i]==0)
 91             topo(i);
 92     make();
 93     for(i=1;i<=n;i++)
 94     {
 95         memset(use,0,sizeof(use));
 96         dfs(i,i);
 97     }
 98     for(i=1;i<=n;i++)
 99         solve(i);
100     printf("\n");
101     return 0;
102 }

P.S. bzoj又挂了

noi 2010 航空管制 贪心

noi 2010 航空管制贪心