首页 > 代码库 > bzoj 2109 & 2535 航空管制 题解
bzoj 2109 & 2535 航空管制 题解
【】
【分析】真的是一道贪心好题。开始我以为是一道大水题。建立拓扑图后(没环就是方便!),直接把最外层设定序号为1,第二层为2,bfs下去即可。。。结果发现:飞行序号不能相同。。。于是开始想。
先考虑第一个问题:打印一个合法序列。我开始是这么想的:
观察每个飞机的最晚飞行序号Ki,因为必定有解,所以我们可以让它的序号就是Ki。然后用它的时间去更新前面的时间(图可以反向建立)。应该可以维护一个大根堆,每次挑出最大的一个进行处理。
【简易代码】
memset(T,0x7f,sizeof(T)); for (i=1;i<=n;i++) if (!num[i]) T[i]=k[i],q.push(make_pair(k[i],i)); while (!q.empty()) { temp=q.top();q.pop(); P=temp.second; for (i=end[P];i;i=a[i].next) { go=a[i].go; if (T[P]-1<T[go]) T[go]=T[P]-1,q.push(make_pair(T[go],go)); } } sort(id+1,id+n+1,cmp); for (i=1;i<=n;i++) if (i<n) printf("%d ",id[i]);else printf("%d\n",id[i]);
考虑第二个问题:求出每个飞机最早的起飞序列。好像嘛,有点~~
我是这么想的:每次枚举一架飞机i,先找到所有在它之前的飞机(以下的dfs进行了一遍flood—fill)
显然这些是一定在前面的。然后我再去找剩余的飞机——统计最晚时间ki的个数。然后枚举可行的时间点j并判断是否可行(二分也可以,不过反正已经O(N)了)。
【简易代码】
for (now=1;now<=n;now++) { memset(T,0,sizeof(T)); memset(deep,0,sizeof(deep)); dfs(now); ans=sum=0; for (i=1;i<=n;i++) if (T[i]&&i!=now) ans++;else if (i!=now) deep[k[i]]++; //for (i=1;i<=k[now];i++) sum+=deep[i]; for (i=1;i<=k[now];i++) { if (ans+sum<i) break; sum+=deep[i]; } printf("%d ",i); }
【思考】啦啦啦~~~可惜,以上的想法都是错的。。。。
第二个有点想通了,因为ki的限制,有些飞机的最晚时间可能的确大于j,但是他们必须立刻起飞,否则就没有时间了。我跑出来的解和标准数据相差的不是很大,可以当骗分用。
【正解】膜拜了VLK的题解——可以把所有的边反向,ki与N取反。这样,最晚时间变成了最早时间,也就是说,枚举到每个点的时候,都可以尽可能的拖晚时间。
【AC代码】
#include<cstdio> #include<cstring> #include<queue> #include<algorithm> #define N 2005 using namespace std; struct arr{int go,next;}a[20005]; int end[N],ord[N],T[N],k[N],dis[N],num[N],id[N],Q[N]; int P,n,m,i,x,y,now,cnt,go,ans,sum; pair<int,int>temp; inline void add(int u,int v) { a[++cnt].go=v;a[cnt].next=end[u];end[u]=cnt; } inline int work(int x) { memcpy(dis,num,sizeof(num)); int h=0,t=0,v,p,i; for (i=p=1;i<=n;i++) { for (;p<=n&&k[v=ord[p]]<i;p++) if (!dis[v]&&v!=x) Q[++t]=v; if (h<t) { v=Q[++h]; for (int j=end[v];j;j=a[j].next) { int go=a[j].go;dis[go]--; if (!dis[go]&&go!=x&&k[go]<i) Q[++t]=go; } } else return t; } return t; } inline bool cmp(int a,int b) { return T[a]<T[b]; } inline bool cmp2(int a,int b) { return k[a]<k[b]; } int main() { scanf("%d%d",&n,&m); for (i=1;i<=n;i++) scanf("%d",&k[i]),k[i]=n-k[i],ord[i]=i; for (i=1;i<=m;i++) { scanf("%d%d",&x,&y); add(y,x);num[x]++; } sort(ord+1,ord+n+1,cmp2); for (i=work(0);i;i--) { printf("%d",Q[i]); if (i>1) printf(" ");else printf("\n"); } for (i=1;i<=n;i++) printf("%d ",n-work(i)); return 0; }
【总结】一道NOI的好题,有时间值得再次回顾!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。