4个家庭去野宴，每个家庭4个人。现有四辆车可以使用，每辆车运输人数有限，汽车1：4个人，汽车2：3个人，汽车3：3个人，汽车4：4个人。并要求每辆车不能运送一个家庭两个以上的人。将该运输尽可能多的人去野宴的问题表述为最大流问题。
第1个回答 推荐于2016-01-25
从左到右，顶点分为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，容量是车的人数限制。
由于每条边都是整数，这个最大流最后解出来也都是整数。本回答被提问者采纳
s：起点
a1、a2、a3、a4：代表4个家庭的4个点
b1、b2、b3、b4：代表4辆车的4个点
t：终点
边：
从s到每个ai，边的容量是家庭人数，也就是说都是4。
从每个ai，到每个bi，一共16条边，容量都是2，因为每个家庭到一辆车上的最多有2人。
从每个bi到t，容量是车的人数限制。
由于每条边都是整数，这个最大流最后解出来也都是整数。本回答被提问者采纳
