访问密码:8位,包含大小写及连续数字段。
给定一个 $n\times m$ 的矩阵,矩阵上每一个点可能是狼、羊或者空地。 你需要在格子的边界修建篱笆,使得任意两个狼与羊的格子不连通。 给一个格子的一条边界修建篱笆,那么篱笆总长度增加 $1$,求篱笆的最短长度。 $n, m\leq 100$.
有 $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 页来讲述网络流的知识,这里详细介绍了几种求最大流的算法。