最小费用最大流问题多个汇点多个源点

最小费用最大流问题多个汇点多个源点可以转化为单源汇点的最小费用最大流问题。具体做法是，将所有的源点汇聚成一个超级源点，将所有的汇点汇聚成一个超级汇点，然后从超级源点向每个源点连一条容量为正无穷大、费用为0的边；从每个汇点向超级汇点连一条容量为正无穷大、费用为0的边；对于原图中的每条边(u,v,c,w)，从u向v连一条容量为c、费用为w的边。这样就得到了一个单源汇点的最小费用最大流问题。可以使用最小费用最大流算法来解决该问题。