一，给定流量F，求最小费用
题意：网络中有两台计算机s,t。现在每秒钟要从s到t传输大小为F的数据到t。该网络中一共有N台计算机，其中有一些靠单向电缆相连接每条电缆用（from,to,cap,cost）表示从from发送给to，，最大容量是cap，单位传输费用是cost。问传输数据最小的花费是多少？
解决最小费用流的一般思路是：每次都沿着最短路进行增广，增广一次之后累加本次增广的总费用，同时修改剩余的流量F，当F≤0时或dist[t]==INF时退出。
利用改进的Dijkstra算法求解
（1）概述：题目要求在存在流量为F的前提下，总花费最少。这类问题就是最小费用流问题。该问题可以采用加入“势函数”后的Dijkstra算法解决。因为对于每条边e=(u,v)，有如下事实成立：h(v)≤h(u)+e.cost(其中h[u]表示s到u的最短距离)。因此令dist[v]=dist[u]+e.cost+h[u]-h[v],。那么所有的dist值必然大于等于0，这样就能用Dijkstra算法求解了。下面代码中用了一个优先队列，每次优先出列dist值小的元素。整个算法的时间复杂度是O(F*ElogV)（F是流量，E是边数，V是顶点数）。
#include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 1000#define INF 100000000typedef pair<int, int>P;//first保存最短距离，second保存顶点的编号struct Edge{int to, cap, cost, rev;//终点，容量（指残量网络中的），费用，反向边编号Edge(int t, int c, int cc, int r) :to(t), cap(c), cost(cc), rev(r){}};int V;//顶点数vector<Edge>G[N];//图的邻接表int h[N];//顶点的势int dist[N];//最短距离int prevv[N];//最短路中的父结点int preve[N];//最短路中的父边void addedge(int from, int to, int cap, int cost){G[from].push_back(Edge( to, cap, cost, G[to].size()));G[to].push_back(Edge( from, 0, -cost, G[from].size() – 1 ));}int min_cost_flow(int s, int t, int f)//返回最小费用{int res = 0;fill(h, h + V, 0);while (f>0)//f>0时还需要继续增广{priority_queue<P, vector<P>, greater<P> >q;fill(dist, dist + V, INF);//距离初始化为INFdist[s] = 0;q.push(P(0, s));while (!q.empty()){P p = q.top(); q.pop();int v = p.second;if (dist[v]<p.first)continue;//p.first是v入队列时候的值，dist[v]是目前的值，如果目前的更优，扔掉旧值for (int i = 0; i<G[v].size(); i++){Edge&e = G[v][i];if (e.cap>0 && dist[e.to]>dist[v] + e.cost + h[v] – h[e.to])//松弛操作{dist[e.to] = dist[v] + e.cost + h[v] – h[e.to];prevv[e.to] = v;//更新父结点preve[e.to] = i;//更新父边编号q.push(P(dist[e.to], e.to));}}}if (dist[t] == INF)//如果dist[t]还是初始时候的INF，那么说明s-t不连通，不能再增广了return -1;for (int j = 0; j<V; j++)//更新hh[j] += dist[j];int d = f;for (int x = t; x != s; x = prevv[x])d = min(d, G[prevv[x]][preve[x]].cap);//从t出发沿着最短路返回s找可改进量f -= d;res += d*h[t];//h[t]表示最短距离的同时，也代表了这条最短路上的费用之和，乘以流量d即可得到本次增广所需的费用for (int x = t; x != s; x = prevv[x]){Edge&e = G[prevv[x]][preve[x]];e.cap -= d;//修改残量值G[x][e.rev].cap += d;}}return res;}int main(){freopen("t.txt", "r", stdin);int m;while (cin >> V >> m){for (int i = 0; i<m; i++){int from, to, cap, cost;cin >> from >> to >> cap >> cost;addedge(from, to, cap, cost);}int s, t, f;cin >> s >> t >> f;cout << min_cost_flow(s, t, f) << endl;}return 0;}二，网络输出最大流时，求出最小的费用
这就是最小费用最大流问题：既要求出最大流，又要求出达到最大流时候的最小费用。一般的解决办法是利用Bellman-Ford算法沿着最短路增广，每增广一次算一次费用，直到不存在最短路为止，此时便找到了最大流，同时也得到了最小费用。为了减少溢出的可能，cost类型改为long long。
利用Bellman-Ford算法求解
（1）概述：整个算法与之前的Bellman-Ford算法差不多，只不过多了一个cost参数而已，注意：初始的网络可以由负权边，但不允许有负权圈，否则算法失效。
#include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 1000#define INF 100000000struct Edge{int from,to,cap,flow,cost;};struct MCMF{int n,m,s,t;vector<Edge>edges;vector<int>G[N];int inq[N];//是否在队列中int d[N];//Bellman-Fordint p[N];//上一条弧int a[N];//可改进量void init(int n){this->n=n;for(int i=0;i<n;i++)G[i].clear();edges.clear();}void addedge(int from,int to,int cap,int cost){edges.push_back((Edge){from,to,cap,0,cost});edges.push_back((Edge){to,from,0,0,-cost});m=edges.size();G[from].push_back(m-2);G[to].push_back(m-1);}bool BellmanFord(int s,int t,int&flow,long long&cost)//沿着最短路增广{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;queue<int>q;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]=min(a[u],e.cap-e.flow);//更新可改进量，等于min{到达u时候的可改进量，e边的残量}if(!inq[e.to]){q.push(e.to);inq[e.to]=1;}}}}if(d[t]==INF)//仍为初始时候的INF，s-t不连通，失败退出return false;flow+=a[t];cost+=(long long)d[t]*a[t];//d[t]一方面代表了最短路长度，另一方面代表了这条最短路的单位费用的大小int u=t;while(u!=s)//逆向修改每条边的流量值{edges[p[u]].flow+=a[t];edges[p[u]^1].flow-=a[t];u=edges[p[u]].from;}return true;}int MincostMaxflow(int s,int t,long long&cost)//返回最大流，同时用引用返回达到最大流时的最小费用{int flow=0;cost=0;while(BellmanFord(s,t,flow,cost));//直到不存在最短路时停止return flow;}};int main(){// freopen("t.txt","r",stdin);MCMF res;int m;while(cin>>res.n>>m){ <pre class="cpp" name="code">res.init();for(int i=0;i<m;i++){int from,to,cap,cost;cin>>from>>to>>cap>>cost;res.addedge(from,to,cap,cost);}long long cost;cin>>res.s>>res.t;cout<<res.MincostMaxflow(res.s,res.t,cost)<<endl;//输出最大流cout<<cost<<endl;//输出达到最大流时的最小费用}return 0;}
人生，一场人喧鼓响的戏，我只是一个平凡的过客，
