最小费用最大流算法; SPFA找最小耗费增广路

admin

最小费用最大流是在流达到最大的情况下,耗费最小的流.
什么意思, 就是贪心的找,每次找耗费最小的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]