本文共 3245 字，大约阅读时间需要 10 分钟。
最小费用最大流就是指网络最大流的集合中找出最小费用的那个最大流。
其基本思想是从某个可行流F出发，找到关于这个流的一个可改进路经P，然后沿着P调整F，对新的可行流试图寻找关于他的可改进路经，如此反复直至求得最大流。现在要找最小费用的最大流，可以证明，若F是流量为V(F)的流中费用最小者，而P是关于F的所有可改进路中费用最小的可改进路，则沿着P去调整F,得到的可行流F'一定是流量为V(F')的所有可行流中的最小费用流。这样，当F是最大流时候，他就是所要求的最小费用最大流。
f是正向流，并且f没有饱和，则还可以继续增加正向流，所有构件的新的残余网络是正向的边，权重是正的单位花费，同时也可以减少f，对应的是反向边，权重是负的单位花费；
f是饱和流，对于新的残余网络，只构件反向边，权重是负的单位花费
f=0,只构件正向边，权重是正的单位花费
整体架构就是用spfa，获得最短增量链
用ff调整流
poj2195:
#include <cstring> #include <iostream> #include <vector> #include <cmath> #include <queue> #include <limits> #include <stdio.h> #include <set> using namespace std; struct pos{ int i; int j; }; int N; int M; //char maphm[100][100]; const int maxNode = 202; //int residal[maxNode][maxNode];//maxInt表示此路不通 //int residalf[maxNode][maxNode]; int capital[maxNode][maxNode];//还剩余的空间[i][j]表示i-->j的剩余容量，[j][i]表示j--->i的剩余容量 //int flow[maxNode][maxNode]; int maxTime[maxNode]; int pre[maxNode]; int minCost[maxNode];//从0到i结点的最小花费 int maxRealNode; int maxInt = numeric_limits<int>::max(); int costMtx[maxNode][maxNode];//单位花费 bool spfa() { memset(maxTime,0,sizeof(maxTime)); memset(pre,-1,sizeof(pre)); queue<int> q; //set<int> s; bool vsd[maxNode]; memset(vsd,false,sizeof(vsd)); vsd[0] = true; q.push(0); minCost[0] = 0; ++maxTime[0]; for(int i=1;i<maxRealNode;++i) minCost[i] = maxInt; while (!q.empty()) { int node = q.front(); q.pop(); vsd[node] = false; for (int i = 0;i<maxRealNode;++i) { if(capital[node][i] && minCost[i] >(minCost[node]+ costMtx[node][i]))//1.如果从node-->i还有容量，即使是负向的容量;2.minCost[node]<maxInt,因为都是在得到较小值后放入队列中 { if(maxTime[i]+1>=maxRealNode) return false; ++maxTime[i]; if(!vsd[i]) { q.push(i); vsd[i] = true; } minCost[i] = minCost[node]+costMtx[node][i]; pre[i] = node; } } } if(minCost[maxRealNode -1]<maxInt) return true; return false; } int min_cost_max_flow() { int minCostAll = 0; while(spfa()) { int e = maxRealNode -1; int minFlow = maxInt; while (e>0) { int preNode = pre[e]; if(minFlow >capital[preNode][e]) minFlow = capital[preNode][e]; e = preNode; } e = maxRealNode - 1; while (e >0) { int preNode = pre[e]; capital[preNode][e] -=minFlow; capital[e][preNode] +=minFlow; minCostAll +=minFlow * costMtx[preNode][e]; e = preNode; } } return minCostAll; } int cost(pos &p1,pos &p2)//m,h { return abs((float)(p1.i-p2.i)) + abs((float)(p1.j-p2.j)); } int main() { //while(cin>>N>>M) while(scanf("%d%d",&N,&M)!=EOF) { //cout<<N<<" "<<M<<endl; if(N==0 && M==0) return 0; char t; vector<pos> m; vector<pos> h; for (int i=0;i<N;++i) { for (int j=0;j<M;++j) { cin>>t; pos post; post.i = i; post.j = j; if(t=='H') h.push_back(post); else if(t =='m') m.push_back(post); } } memset(capital,0,sizeof(capital)); //memset(residal,0,sizeof(residal)); //memset(flow,0,sizeof(flow)); memset(costMtx,0,sizeof(costMtx)); //memset(residalf,0,sizeof(residalf)); int mNum = m.size(); int hNum = h.size()+mNum; maxRealNode = hNum+2; for (int i=1;i<=mNum;++i)//0->i的容量 { capital[0][i] = 1; } for(int i=mNum+1;i<=hNum;++i)//i-->end的容量 capital[i][hNum+1] = 1; for (int i=0;i<m.size();++i) { for (int j=0;j<h.size();++j) { capital[i+1][mNum+1+j] = 1; costMtx[i+1][mNum+1+j] = cost(m[i],h[j]); costMtx[mNum+1+j][i+1]= -costMtx[i+1][mNum+1+j]; } } cout<<min_cost_max_flow()<<endl; } /*scanf("%d%d",&N,&M); cout<<N<<" "<<M<<endl;*/ return 0; }
转载地址：http://obeti.baihongyu.com/