最小费用最大流是在流达到最大的情况下,耗费最小的流.
什么意思, 就是贪心的找,每次找耗费最小的s-t 路, 给这条路增最大的流.
然后再找耗费最小的s-t路, 继续增流.
流不分贵贱(先后次序), 只要总流未超过最小割, 就肯定还能有一条路增流,最终到达最大流.
但是,这个过程每次增流都是增加耗费最小的流,这样操作下去,最后的最大流就是耗费最小的最大流了.
初始化时,(i,j)有费用k,则(j,i)有费用-k, 其他边的费用均为0即可, 无关紧要. 因为只有存在增广路的情况下才可能用到这些费用,既然没有路径, 这些费用值是不会用到的, 很安全, 甚至你可以随便给它赋值.
参见poj2516 2195 2135。
[code=Cpp width=700px]
#include <iostream>
#include <queue>
using namespace std;
/*********************************/
* 最小割最大流算法
* 可以在求得最大流的同时获取最小割集S,T
* 邻接矩阵存储各类信息
/*********************************/
#define INF 1000000
const int MAXN=1000;
int cap[MAXN][MAXN]; //容量 ,没有边为0
int flow[MAXN][MAXN]; //流量
int cost[MAXN][MAXN]; //耗费矩阵
int p[MAXN]; //增广路前驱
int d[MAXN]; //s-t路径最小耗费
bool inq[MAXN]; //队列标记
int n; // 顶点数目
int f; //最大流
int s,t; //源点,汇点
int c; //最大流下最小耗费
/*********************************/
* 邻接矩阵读入图数据
* 例子:
4
0 2 1 0
0 0 1 1
0 0 0 1
0 0 0 0
0 2 5 0
-2 0 2 3
-5 -2 0 1
0 -3 -1 0
注明: 费用矩阵是对称的,有i,j的费用,则j,i费用为其相反数
/*********************************/
void readG()
{
cin>>n;
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
cin>>cap[j];
}
}
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
cin>>cost[j];
}
}
}
/*********************************/
* void minCmaxF()
* 最小费用最大流算法
* SPFA()算法找最小耗费增广路
* SPFA()其实是Bellman的一个小变形
* 求得的f一定是最大流,求得的c是最大流下最小耗费
/*********************************/
void minCmaxF()
{
cin>>s>>t;
queue<int> q;
memset(flow,0,sizeof(flow));
c=f=0;
for(;;)
{
memset(inq,0,sizeof(inq));
for(int i=0;i<n;++i)
{
d= i==s ? 0:INF;
}
q.push(s);
while(!q.empty())
{
int u=q.front(); q.pop();
inq=false;
for(int v=0;v<n;v++)
{
if(cap[v]-flow[v]>0&&d[v]>d+cost[v])
{
d[v]=d+cost[v];
p[v]=u;
if(!inq[v])
{
inq[v]=true;
q.push(v);
}
}
}
}
if(d[t]==INF)
{
cout<<"最大流:"<<f<<",最小耗费:"<<c<<endl;
break;
}
int a=INF;
for(int u=t;u!=s;u=p)
{
if(cap[p]-flow[p]<a)
{
a=cap[p]-flow[p];
}
}
for(int u=t;u!=s;u=p)
{
flow[p]+=a;
flow[p]-=a;
}
c+=d[t]*a;
f+=a;
}
}
int main()
{
readG();
minCmaxF();
return 0;
}
[/code]
学习最小费用最大流前,需要学习最大流算法。在最大流算法中,没有考虑边的费用问题。在MinCostMaxFlow中,引入了费用的概念:cij表示边(i,j)单位流量的费用。在满足流量=v(f)的同时,并且要求费用最少。
最小费用最大流的迭代算法:
1.求出从s到t的最小费用通路(spfa)和通路的最大流量f。
2.让通路上的边(i,j)流量减去f;添加反向边(j,i),容量为f,费用为-cost(i,j)。
3.重复1,2,直到从s到t的流量=v(f)或者再也找不到从s到t的最小费用道路为止。
最小费用最大流算法还可以解决二分图最优匹配。 最小费用最大流模板: [code=Cpp width=700px]const int size = 1102;
const int INF = 0x7fffffff;
struct Edge
{
int to;
int vol;
int cost;
int next;
}e[size*40];
int index[size];
int edgeNum;
int pre[size], pos[size];
int dis[size], que[size*10];
bool vis[size];
void insert(int from, int to, int vol, int cost)
{
e[edgeNum].to = to;
e[edgeNum].vol = vol;
e[edgeNum].cost = cost;
e[edgeNum].next = index[from];
index[from] = edgeNum++;
e[edgeNum].to = from;
e[edgeNum].vol = 0;
e[edgeNum].cost = -cost;
e[edgeNum].next = index[to];
index[to] = edgeNum++;
}
bool spfa(int s, int t)
{
int i;
memset(pre, -1, sizeof(pre));
memset(vis, 0, sizeof(vis));
int head, tail; head = tail = 0;
for(i = 0; i < size; i++)
dis = INF;
que[tail++] = s;
pre = s;
dis = 0;
vis = 1;
while(head != tail)
{
int now = que[head++];
vis[now] = 0;
for(i = index[now]; i != -1; i = e.next)
{
int adj = e.to;
if(e.vol > 0 && dis[now] + e.cost < dis[adj])
{
dis[adj] = dis[now] + e.cost;
pre[adj] = now;
pos[adj] = i;
if(!vis[adj])
{
vis[adj] = 1;
que[tail++] = adj;
}
}
}
}
return pre[t] != -1;
}
int MinCostFlow(int s, int t, int flow)
{
int i;
int cost = 0;
flow = 0;
while(spfa(s, t))
{
int f = INF;
for(i = t; i != s; i = pre)
if (e[pos].vol < f) f = e[pos].vol;
flow += f; cost += dis[t] * f;
for(i = t; i != s; i = pre)
{
e[pos].vol -= f;
e[pos ^ 1].vol += f;
}
}
return cost; // flow是最大流值
}
[/code]
|