Question

运筹学最大流问题建模4个家庭去野宴,每个家庭4个人.现有四辆车可以使用,每辆车运输人数有限,汽车1：4个人,汽车2：3个

Answer 1

从左到右,顶点分为4部分：

s：起点

a1、a2、a3、a4：代表4个家庭的4个点

b1、b2、b3、b4：代表4辆车的4个点

t：终点

边：

从s到每个ai,边的容量是家庭人数,也就是说都是4.

从每个ai,到每个bi,一共16条边,容量都是2,因为每个家庭到一辆车上的最多有2人.

从每个bi到t,容量是车的人数限制.

由于每条边都是整数,这个最大流最后解出来也都是整数.