题目内容

小红是公司里的一名领导，他负责组织今年的团建活动。这个团建活动很重要，因为公司里的员工们都非常忙碌，很少有机会聚在一起，所以这次活动是大家期待已久的。

为了让所有人都能够参加到自己想要参加的活动，小红收集了所有人的意愿，并准备了三个不同的活动：$A$、$B$ 和 $C$，每个活动都有不同的人数上限和参加费用。

为了让所有人都能参加到自己想要参加的活动，小红收集了所有人的投票结果。现在他希望在满足所有人的意愿的前提下，尽可能地降低团建的总费用。

但是，小红面临着一个难题，因为人们的意愿各不相同，他需要考虑每个人的选择，才能做出最好的决策。

思路

这道题的解法是最小费用最大流。具体算法的原理可以去百度学习。这道题主要讨论如何对图进行建模。

我们发现一共N个人，每个人都有想去的地方，然后题意要我们保证N个人都能满足要求，然而每个地方都有人数限制。那么从这一个题意出发，很容易想到网络流的解法。

定义源点$S = 0$， 汇点$T= n + 4$

$N$个人，我们定义点为$[1,n]$,3个地方，我们定义点为$[n+1,n+3]$.