「网络流 24 题」方格取数-二分图最大独立集

在一个有 $m \times n$ 个方格的棋盘中,每个方格中有一个正整数。

现要从方格中取数,使任意 $2$ 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。

「网络流 24 题」魔术球-二分图最大匹配

假设有 $n$ 根柱子,现要按下述规则在这 $n$ 根柱子中依次放入编号为 $1, 2, 3, 4, \cdots$ 的球。

  1. 每次只能在某根柱子的最上面放球。
  2. 在同一根柱子中,任何 $2$ 个相邻球的编号之和为完全平方数。

试设计一个算法,计算出在 $n$ 根柱子上最多能放多少个球。

「网络流 24 题」最小路径覆盖-二分图最大匹配

给定有向图 $G = (V, E)$。设 $P$ 是 $G$ 的一个简单路(顶点不相交)的集合。如果 $V$ 中每个顶点恰好在 $P$ 的一条路上,则称 $P$ 是 $G$ 的一个路径覆盖。 $P$ 中路径可以从 $V$ 的任何一个顶点开始,长度也是任意的,特别地,可以为 $0$ 。 $G$ 的最小路径覆盖是 $G$ 的所含路径条数最少的路径覆盖。

设计一个有效算法求一个有向无环图 $G$ 的最小路径覆盖。

「网络流 24 题」搭配飞行员-二分图最大匹配

飞行大队有若干个来自各地的驾驶员,专门驾驶一种型号的飞机,这种飞机每架有两个驾驶员,需一个正驾驶员和一个副驾驶员。由于种种原因,例如相互配合的问题,有些驾驶员不能在同一架飞机上飞行,问如何搭配驾驶员才能使出航的飞机最多。

因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×