[NOI2010] 航空管制
link正难则反。既然限制最后的起飞时间不太好做，考虑建反图，然后把限制转化成什么时候之后才能起飞。于是第一问可以暴力寻找限制时间最大的点（如果它都飞不起来那么其它点更别想了）。这就解释了为什么要建反图，因为在原图上随着时间的推移有些点会被封闭起来，拖得越久越不利，所以不好弄；而反图上则是随着时间解放一些点，是否可行一目了然，就算现在不行等一等总会等到的，所以和时间关系不大。至于第二问，考虑在第一问的过程中强制不选那个点，如果选不动了（所有点都无法转移或者干脆就剩它一个点）就说明它最早可以在那个时间出来。
#include//#define zczcconst int N=2010;const int M=10010;using namespace std;inline void read(int &wh){ wh=0;int f=1;char w=getchar(); while(w'9'){if(w=='-')f=-1;w=getchar();} while(w='0'){wh=wh*10+w-'0';w=getchar();} wh*=f;return;}struct edge{ int t,next;}e;int head,esum;inline void add(int fr,int to){ e[++esum]=(edge){to,head};head=esum;}int m,a,n,d,an;struct node{ int id,ti;};inline bool operator s1.ti;}priority_queueq;signed main(){ #ifdef zczc freopen("in.txt","r",stdin); #endif read(m);read(n);int s1,s2; for(int i=1;i
页:
[1]