标签: 网络流

2 篇文章

Luogu – 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$.
求最大总收益。
网络流 – 最大流
网络流在 OI 中是显得尤为重要的。在《算法导论》中就用了 35 页来讲述网络流的知识,这里详细介绍了几种求最大流的算法。