最小费用最大流
有了上一篇文章最大流的基础，理解最小费用最大流就很容易了，但是我还是想了挺久的。当我看到最小费用最大流问题这篇文章，才开始觉悟。于是做了如下实现。
/*每次找出最短路径（该路径的单位费用和最小）记录该路径（next数组）直到找不出这样一条路径(实际上是没有到达终点的路，因为图中的路是会不停的变动)。我们这里的是Distance[0]>=MAX*/#include<iostream>using namespace std;#define MAX 1024int nodes,edges;//节点数和边数int capacity[MAX][MAX];//节点之间的流量int cost[MAX][MAX];//节点之间的单位费用int minCost=0;//统计最小费用int next[MAX];//为了记录最短路径int Distance[MAX];//表示每个节点到终点的费用inline int min(int a,int b){return a<b?a:b;}void resetThePath()//找出最短路径,这里还需优化。{int i,j;for(i=0;i<nodes-1;i++)Distance[i]=MAX;Distance[nodes-1]=0;next[nodes-1]=-1;for(i=nodes-1;i>=0;i--){for(j=0;j<nodes;j++){if(cost[j][i]!=MAX){if(Distance[j]>(Distance[i]+cost[j][i])){Distance[j]=Distance[i]+cost[j][i];next[j]=i;}}}}for(i=nodes-1;i>=0;i--){for(j=0;j<nodes;j++){if(cost[j][i]!=MAX){if(Distance[j]>(Distance[i]+cost[j][i])){Distance[j]=Distance[i]+cost[j][i];next[j]=i;}}}}void minCostMaxFlow(){while(1){int i;resetThePath();if(Distance[0]>=MAX)//没有最短路径break;int increase=MAX;//本次最短路径中的流量for(i=0;next[i]!=-1;i=next[i]){increase=min(increase,capacity[i][next[i]]);}for(i=0;next[i]!=-1;i=next[i])//改变图的路径信息{capacity[i][next[i]]-=increase;capacity[next[i]][i]+=increase;if(cost[next[i]][i]==MAX)cost[next[i]][i]=cost[i][next[i]]*(-1);if(!capacity[i][next[i]])cost[i][next[i]]=MAX;}minCost+=Distance[0]*increase;}}void main(){while(1){cin>>nodes>>edges;int i,j;for(i=0;i<nodes;i++){for(j=0;j<nodes;j++)capacity[i][j]=0;for(j=0;j<nodes;j++)cost[i][j]=MAX;}int firstnode,secondnode,capa,cos;for(i=0;i<edges;i++){cin>>firstnode>>secondnode>>capa>>cos;capacity[firstnode][secondnode]=capa;cost[firstnode][secondnode]=cos;}minCostMaxFlow();cout<<minCost<<endl;}}