网络流 最小费用最大流问题

下面给网络里增加一个因素：费用。假设每条边除了有一个容量限制以外，还有一个单位流量所需的费用。在最小费用流问题中，平行边变得有意义：可能会有两条从u到v的弧，费用分别为1和2。在没有费用的情况下，我们可以把二者合并，但由于费用的出现，我们无法合并这两条弧。再如，若边（u，v）和（v，u）均存在，且费用都是负数，则“同时从u流向v和从v流向u”是个很不错的主意。为了方便叙述算法，我们先假定图中不存在平行边和反向边。这样就可以用邻接矩阵cap和cost保存各边的容量和费用。为了便于增广，对于一条边（u，v），我们规定cap[u][v]=0并且cost[v][u]=-cost[u][v]，表示沿着(u,v)的相反方向增广时，费用减少cost[u][v]。下面直接给出算法，和EK算法类似，但每次用Bellman-Ford算法，而非BFS找增广路。只要初始流是该流量下最小费用可行流，每次增广后的新流都是新流量下的最小费用流。另外费用值是可正可负的。

queue q;
int d[maxn];
memset(flow, 0, sizeof(flow));
c = f = 0;
while(true){//bellman-ford算法开始，在残留网络中找s-t最短路bool inq[manx];for(int i = 0; i < n; i++) d[i] = (i==s ? 0 : INF);memset(inq,0,sizeof(inq));q.push(s);while(!q.empty)){int u = q.front(),q.pop();for(int i = 0; i < n; i++){if(cap[u][i]>flow[u][i] && d[i]>d[u]+cost[u][i]){d[i] = d[u]+cost[u][i];p[i] = u;if(!inq[i]){q.push(i);inq[i] = 1;}}}} //bellman-ford算法结束if(d[t]==INF) break; //说明汇点不可达，辨明当前流已经是最小费用最大流int a = INF;for(int i = t; i!=s; i = p[i]) a = (a>cost[p[i]][i]-flow[p[i]][i] ? cost[p[i]][i]-flow[p[i]][i] : a);for(int i = t; i!=s; i = p[i]){flow[p[i]][i] += a;flow[i][p[i]] -= a;}c += d[t]*a;f += a;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！