题解

题目描述

某公司有 $2$ 个仓库（用 $A$ 和 $B$ 表示），需要给 $m$ （ $m$ 为偶数）个营业网点各配送一件货物。假设每个仓库正好都有 $\tfrac{m}{2}$ 件货物，配送给不同营业网点的费用使用一个二维数组 $\mathit{cost}$ 表示，其中

\mathit{cost}[i]=[A_i,B_i]

表示第 $i$ 个营业网点从 $A$ 仓发货的运费为 $A_i$ ，从 $B$ 仓库发货的费用为 $B_i$ 。请计算 $m$ 件货物配送的最低费用，要求每个营业网点都有一件货物送到。

一家公司设有两个仓库，分别命名为 $A$ 和 $B$ 。公司需要向 $M$ 个营业网点各配送一件商品，且 $M$ 保证为偶数。两个仓库在配送开始前各有 $M/2$ 件商品库存。

不同营业网点的配送费用通过二维数组 $cost$ 表示。对于第 $i$ 个营业网点， $cost[i] = [A_i, B_i]$ ，其中 $A_i$ 表示从仓库 $A$ 发货到该网点的运费， $B_i$ 表示从仓库 $B$ 发货到该网点的运费。

请为每个营业网点选择一座发货仓库，使得所有营业网点都恰好收到一件商品，并且两个仓库各发出全部的 $M/2$ 件商品。计算所有可行分配方案中的最小总运费。

约束条件：