本文主要是介绍再谈最小费用最大流算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
我在之前的博客中讲过最小费用最大流算法，但是实现的时候使用的是邻接矩阵，无法支持多重边。下面我们仍然实现这个算法，但采用的是新的数据结构，代码如下
struct Edge {int from, to, cap, flow, cost;
};int n,m,s,t;
vector<Edge> edges;
vector<int> G[maxn];
int inq[maxn]; //是否在队列中
int d[maxn]; //Bellman-Ford
int p[maxn]; //上一条弧
int a[maxn]; //可改进量void AddEdge (int from, int to, int cap, int cost){edges.push_back((Edge){from,to,cap,0,cost});edges.push_back((Edge){from,to,0,0,-cost});m = edges.size();G[from].push_back(m-2);G[to].push_back(m-1);
}int flow,cost;bool Bellford (){queue<int> q;for(int i = 0; i < n; i++) d[i]=INF:memset(inq,0,sizeof(inq));d[s] = 0;inq[s]=1;p[s]=0;a[s]=INF;q.push(s);while(!q.empty()){int u = q.front(), q.pop();inq[u] = 0;for(int i = 0; i < G[u].size(); i++){Edge& e = edges[G[u][i]];if(e.cap>e.flow && d[e.to]>d[u]+e.cost){d[e.to] = d[u]+e.cost;p[e.to] = G[u][i];a[e.to] = (a[u]>e.cap-e.flow ? e.cap-e.flow : a[u])if(!inq[e.to]){q.push(e.to); inq[e.to] = 1;}}}}if(d[t]==INF) return false;for(int i = t; i!=s; i = edges[p[i]].from){edges[p[i]].flow += a[t];edges[p[i]^1].flow -= a[t];}flow += a[t];cost += a[t]*d[t];return true;
}//主过程：int main (){flow = 0, cost = 0;while(Bellford());return cost;}这篇关于再谈最小费用最大流算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
