标签: 费用流

1 篇文章

洛谷 – P4452 – [国家集训队]航班安排
有 $K$ 架飞机,$N$ 个机场,其中 $1$ 号为基地机场。
每天 $0$ 时刻,飞机才可以从基地机场起飞,并且不晚于 $T$ 时刻回到基地机场。
对于 $\forall i, j$,题目给定 $t_{i, j}$ 表示从 $i$ 空载飞到 $j$ 需要的时间,$f_{i, j}$ 表示从 $i$ 空载飞到 $j$ 需要的费用。
有 $M$ 个包机请求,给定 $(a, b, s, t, c)$,表示在 $s$ 时刻从 $a$ 机场起飞,可以恰好在 $t$ 时刻到达 $b$ 机场,净获利 $c$.
求最大总收益。