机场

判断无解直接差分即可。

易得知,a型停机位严格优于b型停车位。

结论1:只能从a型停机位转到b型停机位。

否则既要多付切换费,也要占用a型停机位。

结论2:一架飞机最多切换一次停机位。

结论3:b的值可以被视为inf

因为如果b被填满了,还能通过a继续填。

结论4:如果飞机进行切换,则肯定在登机时间+1就切换

由于b=inf,不占用a型停机位。

所以根据结论1,2,可以得知飞机只有一直在a,b,登机后马上从a切换到b三种选择。

先假设所有飞机都占用b型停机位。

然后再考虑一些改成占用a型停车位的情况。

如果一直在a型停车位,则要在[s,t)占用a型停车位,代价减少x

如果从a转到b,则要在s时间占用停车位,代价减少x-floor(px)

实际上就是有一些变量和约束,每个约束的形式是使得一些变量的和要<=一个值,求费用最小值。

使用网络流解线性规划:使用志愿者招募的方法即可,但是i+1->i要变成i->i+1

原文地址:https://www.cnblogs.com/cszmc2004/p/12976331.html