注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-[Noi2010]Plane 航空管制2(贪心+并查集+拓扑排序)  

2014-06-25 12:20:00|  分类: oi,bzoj,贪心,并 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2535


事实上这个就是航空管制,只是前面那个没有SPJ没法AC而已额。。。

首先对于第一个问题,对于一对限制a,b,要求a比b先起飞,在一个有向图中连边b->a,这样之后进行一次拓扑排序,尽量把起飞 顺序放后,可以发现在有解情况下,这样一定可以出解;

对于第二个问题,考虑到其他航班的影响,我们希望当前航班除外的都尽量靠后,但是可以由当前航班代表的节点到达的节点除外,删去这些点之后再做一次第一问,那么剩下的所有空位中最后一个就是答案了。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <bitset>

  •  

  • using namespace std ;

  •  

  • #define travel( x ) for ( edge *p = head[ x ] ; p ; p = p -> next )

  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

  • #define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )

  •  

  • const int maxn = 2010 , maxm = 10100 ;

  •  

  • struct edge {

  •     edge *next ;

  •     int t ;

  • } E[ maxm ] ;

  •  

  • edge *pt = E , *head[ maxn ] ;

  •  

  • inline void addedge( int s , int t ) {

  •     pt -> t = t , pt -> next = head[ s ] ; head[ s ] = pt ++ ;

  • }

  •  

  • int father[ maxn ] , n , m , ti[ maxn ] ;

  •  

  • inline int getfa( int now ) {

  •     int i = now ; for ( ; father[ i ] ; i = father[ i ] ) ;

  •     for ( int j = now , k ; father[ j ] ; k = father[ j ] , father[ j ] = i , j = k ) ;

  •     return i ;

  • }

  •  

  • int d[ maxn ] , sta[ maxn ] , tp , dp[ maxn ] , ans[ maxn ] ;

  •  

  • inline void Dp( int del ) {

  •     rep( i , n ) d[ i ] = ans[ i ] = father[ i ] = 0 , dp[ i ] = min( n , ti[ i ] ) ;

  •     rep( i , n ) travel( i ) ++ d[ p -> t ] ;

  •     tp = 0 ;

  •     rep( i , n ) if ( ! d[ i ] ) sta[ ++ tp ] = i ;

  •     int now , pos ;

  •     while ( tp ) {

  •         if ( ( now = sta[ tp -- ] ) == del ) continue ;

  •         pos = getfa( dp[ now ] ) ; ans[ pos ] = now , father[ pos ] = pos - 1 ;

  •         travel( now ) {

  •             dp[ p -> t ] = min( dp[ p -> t ] , dp[ now ] ) ;

  •             if ( ! ( -- d[ p -> t ] ) ) sta[ ++ tp ] = p -> t ;

  •         }

  •     }

  • }

  •  

  • int main(  ) {

  •     memset( head , 0 , sizeof( head ) ) ;

  •     scanf( "%d%d" , &n , &m ) ;

  •     rep( i , n ) scanf( "%d" , ti + i ) ;

  •     while ( m -- ) {

  •         int s , t ; scanf( "%d%d" , &t , &s ) ;

  •         addedge( s , t ) ;

  •     }

  •     Dp( 0 ) ;

  •     rep( i , n ) printf( "%d " , ans[ i ] ) ; printf( "\n" ) ;

  •     rep( i , n ) {

  •         Dp( i ) ;

  •         DOWN( i , n , 1 ) if ( ! ans[ i ] ) {

  •             printf( "%d " , i ) ; break ;

  •         }

  •     }

  •     printf( "\n" ) ;

  •     return 0 ;

  • }



  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017