「网络流 24 题」数字梯形-费用流

给定一个由 $n$ 行数字组成的数字梯形如下图所示。梯形的第一行有 $m$ 个数字。从梯形的顶部的 $m$ 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。

分别遵守以下规则:

  1. 从梯形的顶至底的 $m$ 条路径互不相交;
  2. 从梯形的顶至底的 $m$ 条路径仅在数字结点处相交;
  3. 从梯形的顶至底的 $m$ 条路径允许在数字结点相交或边相交。

「网络流 24 题」餐巾计划-费用流

一个餐厅在相继的 $n$ 天里,每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$ 块餐巾。餐厅可以购买新的餐巾,每块餐巾的费用为 $P$ 分;或者把旧餐巾送到快洗部,洗一块需 $M$ 天,其费用为 $F$ 分;或者送到慢洗部,洗一块需 $n$ 天,其费用为 $S$ 分($S < F$)。

每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 $n$ 天中餐巾使用计划,使总的花费最小。

常见最小费用最大流算法学习笔记

众所周知,最小费用最大流向来是一个算法很多的问题,下面总结了几个常用的最小费用最大流算法。

「NOI2012」美食节-费用流

美食节共有$n$种不同的菜品,每个同学都点了一份在这$n$中菜品中的菜。总共有$m$个厨师来制作这些菜品。厨师们会按照要求的顺序进行制作,并且每次只能制作一人份。第$j$个厨师制作第$i$种菜品的时间记为$t_{i,j}$。每个同学的等待时间为所有厨师开始做菜起,到自己那份菜品完成为止的时间总长度。总等待时间为所有同学的等待时间之和。

已知共有$n$种菜品,第$i$种菜品需要做$p_i$份,共有$m$个厨师。请计算出最小的总等待时间是多少。

「CQOI2012」交换棋子-费用流

有一个 $n$ 行 $m$ 列的黑白棋盘,你每次可以交换两个相邻格子(相邻是指有公共边或公共顶点)中的棋子,最终达到目标状态。要求第 $i$ 行第 $j$ 列的格子只能参与 $m_{i,j}$ 次交换。

输出仅一行,为最小交换总次数。如果无解,输出 $-1$ 。

「SDOI2011」工作安排-费用流

你的公司需要提供$n$类产品,其中第$i$类产品共需要$C_{i}$件。公司共有$m$名员工。员工能够制造的产品种类有所区别,我们用一个由$0$和$1$组成的$m\times n$的矩阵$\mathbb {A}$来描述每名员工能够制造哪些产品。

对于员工$i$,给出$S_i$。定义他的愤怒值与他制作的产品数量之间的函数是一个$S_i+1$段的分段函数。设$T_{i,0}=0$,$T_{i,S_{i+1}}=+\infty$,那么当他制造第$[T_{i,j-1}+1,T_{i,j}]$件产品时,每件产品会使他的愤怒值增加$W_{i,j}$, $1\leq j\leq S_{i+1}$。保证$0<W_{i,j} < W_{i,j+1}, \; 0 < T_{i,j} < T_{i,j+1}$。

你的任务是制定出一个产品的分配方案,使得订单条件被满足,并且所有员工的愤怒值之和最小。

「ZJOI2010」网络扩容-网络流-费用流

给定一张有向图,每条边都有一个容量 $C$ 和一个扩容费用 $W$ 。这里扩容费用是指将容量扩大 $1$ 所需的费用。

现在请你编写一个程序求出:

  1. 在不扩容的情况下, $1$ 到 $N$ 的最大流;
  2. 将 $1$ 到 $N$ 的最大流增加 $K$ 所需的最小扩容费用。
Your browser is out-of-date!

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

×