「GMOJ 3447」摘取作物

Description

$n\times m$ 的矩阵,每行最多选取两个数,每列最多选取两个数,每个数至多选一次,问价值和最大多少。
$n, m\leqslant 30$

Solution

费用流模型。
从原点$s$出发,到左边$n$个点的容量为$2$,费用为$0$,表示每行最多选$2$个数。中间有$n\times m$条边连到右边$m$个点,容量为$1$,费用为$a_{i,j}$,表示每个数只能选$1$次,权值为$a_{i,j}$。右边$m$个点连到汇点$t$,容量为$2$,费用为$0$,表示每列最多选$2$块地。

每次找最大费用增广路,直到没有费用大于$0$的增广路为止。此时的费用之和即为作物价值之和的最大值。要注意此时的流量可能还没有达到最大,但继续增大流量已经不能使费用之和增大了,所以此时对应的选地方案就是最佳方案了。spfa跑一跑就行了

「BZOJ 1419」Red is good

Description

桌面上有$R$张红牌和$B$张黑牌,随机打乱顺序后放在桌面上,开始一张一张地翻牌,翻到红牌得到$1$美元,黑牌则付出$1$美元。可以随时停止翻牌,在最优策略下平均能得到多少钱。
$R,B\leqslant 10^5$


- 阅读全文 -