反复寻找费用最小路径，然后在该路径上使流量增大；寻找最小费用路径时，不考虑剩余容量为 0 的边；虽然网络流图是有向图，但是为了寻找包含反向边的路径，对每条正向边都有可能生成出反向边（当正向边上有流量时，就有容量等于流量的反向边）；
NetworkFlowGraph.h 类头文件：
[cpp]
/*
* NetworkFlowGraph.h
*
* Created on: 2013-1-22
* Author: qichi
*/
#ifndef NETWORKFLOWGRAPH_H_
#define NETWORKFLOWGRAPH_H_
#define MAXVAL (1.0e8)
#define MINVAL (1.0e-6)
class NetworkFlowGraph {
private:
int m_num; // number of vertex
int m_s; // source point
int m_t; // destination point
double ** m_cap; // the max capability of an edge
double ** m_price; // the unit price of an edge
double ** m_vol; // the surplus capability of an edge
int *m_prev; // the previous point
double *m_dist; // the distance from s to each point
double m_cost; // current cost
double m_flow; // current flow
public:
NetworkFlowGraph(int n, int s, int t);
virtual ~NetworkFlowGraph();
public: www.zzzyk.com
void insert(int i, int j, int cap, int price);
bool min_cost_path(double &price);
bool min_cost_flow(double desired, double &maxflow, double &mincost);
void min_cost_max_flow(double &maxflow, double &mincost);
void printMatrix();
void printPath();
};
#endif /* NETWORKFLOWGRAPH_H_ */
NetworkFlowGraph.cpp 类实现：
[cpp]
/*
* NetworkFlowGraph.cpp
*
* Created on: 2013-1-22
* Author: qichi
*/
#include "NetworkFlowGraph.h"
#include <string.h>
#include <iostream>
NetworkFlowGraph::NetworkFlowGraph(int n, int s, int t) {
m_num = n;
m_s = s;
m_t = t;
m_cap = new double*[n];
m_cap[0] = new double[n*n];
m_price = new double*[n];
m_price[0] = new double[n*n];
m_vol = new double*[n];
m_vol[0] = new double[n*n];
for ( int i=1; i<n; i++ ) {
m_cap[i] = m_cap[i-1]+n;
m_price[i] = m_price[i-1]+n;
m_vol[i] = m_vol[i-1]+n;
}
m_prev = new int[n];
m_dist = new double[n];
m_cost = 0;
m_flow = 0;
memset(m_cap[0],0,n*n*sizeof(double));
memset(m_price[0],0,n*n*sizeof(double));
memset(m_vol[0],0,n*n*sizeof(double));
}
NetworkFlowGraph::~NetworkFlowGraph() {
delete m_cap[0];
delete m_price[0];
delete m_vol[0];
delete m_cap;
delete m_price;
delete m_vol;
}
void NetworkFlowGraph::insert(int i, int j, int cap, int price) {
if ( i < m_num && j < m_num ) {
m_cap[i][j] = cap;
m_vol[i][j] = cap;
m_price[i][j] = price;
m_price[j][i] = -price;
}
}
bool NetworkFlowGraph::min_cost_path(double &price) {
for ( int i=0; i<m_num; i++ ) {
m_dist[i] = MAXVAL;
m_prev[i] = -1;
}
m_dist[m_s] = 0;
bool updated = false;
do {
updated = false;
for ( int i=0; i<m_num; i++ ) {
if ( m_dist[i] < MAXVAL - MINVAL ) {
for ( int j=0; j<m_num; j++ ) {
// only consider edges with surplus volume
if ( m_vol[i][j]>MINVAL ) {
if ( m_dist[j] > m_dist[i] + m_price[i][j] ) {
m_dist[j] = m_dist[i] + m_price[i][j];
m_prev[j] = i;
updated = true;
}
}
}
}
}
} while (updated);
price = m_dist[m_t];
return (m_prev[m_t]!=-1);
}
bool NetworkFlowGraph::min_cost_flow(double desired, double &maxflow, double &mincost){
