标签: 网络流

4 篇文章

洛谷 – P2598 – [ZJOI2009]狼和羊的故事
给定一个 $n\times m$ 的矩阵,矩阵上每一个点可能是狼、羊或者空地。
你需要在格子的边界修建篱笆,使得任意两个狼与羊的格子不连通。
给一个格子的一条边界修建篱笆,那么篱笆总长度增加 $1$,求篱笆的最短长度。
$n, m\leq 100$.
洛谷 – 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 页来讲述网络流的知识,这里详细介绍了几种求最大流的算法。