bzoj1745[Usaco2005 oct]Flying Right 飞行航班*

bzoj1745[Usaco2005 oct]Flying Right 飞行航班

题意：

n个农场，有k群牛要从一个农场到另一个农场（每群由一只或几只奶牛组成）飞机白天从农场1到农场n，晚上从农场n到农场1，上面有c个座位，问最多可以满足多少只牛的要求。n≤10000，k≤50000，c≤100。

题解：

用类似贪心的方法做，现将每个农场出发的牛组织成链表。先求早上：当飞机到达每个农场时，先让到达的奶牛下机，接着如果飞机未满，则将其填满，之后枚举剩下的奶牛，如果它们的目的地比坐在飞机上面的奶牛目的地近，就将其替换为当前奶牛，这一过程可以用multiset维护。晚上所有过程都倒过来再做一次即可。

代码：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <set>

 #define inc(i,j,k) for(int i=j;i<=k;i++)

 #define maxn 10010

 using namespace std;

 inline int read(){

     char ch=getchar(); int f=,x=;

     while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}

     while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

     return f*x;

 }

 multiset<int,greater<int> >st1;

 multiset<int>st2;

 int n,m,k,now,ans; struct nd{int t,w,n;}nds[][maxn*]; int ess[],g[][maxn];

 int main(){

     n=read(); m=read(); k=read();

     inc(i,,n){

         int x=read(),y=read(),z=read();

         if(x<y)nds[][++ess[]]=(nd){y,z,g[][x]},g[][x]=ess[];

         else nds[][++ess[]]=(nd){y,z,g[][x]},g[][x]=ess[];

     }

     now=;

     inc(i,,m){

         if(st1.find(i)!=st1.end()){int x=st1.erase(i); ans+=x; now-=x;}

         for(int j=g[][i];j;j=nds[][j].n){

             while(now<k&&nds[][j].w)st1.insert(nds[][j].t),nds[][j].w--,now++;

             if(now==k){

                 while(*st1.begin()>nds[][j].t&&nds[][j].w)

                     st1.erase(st1.begin()),st1.insert(nds[][j].t),nds[][j].w--;

             }

         }

     }

     now=;

     for(int i=m;i>=;i--){

         if(st2.find(i)!=st2.end()){int x=st2.erase(i); ans+=x; now-=x;}

         for(int j=g[][i];j;j=nds[][j].n){

             while(now<k&&nds[][j].w)st2.insert(nds[][j].t),nds[][j].w--,now++;

             if(now==k){

                 while(*st2.begin()<nds[][j].t&&nds[][j].w)

                     st2.erase(st2.begin()),st2.insert(nds[][j].t),nds[][j].w--;

             }

         }

     }

     printf("%d",ans); return ;

 }

20161115