落絮飞雁的个人网站
图论:最小费用流与Bellman-Ford算法
图论:最小费用流与Bellman-Ford算法

最小传输费用问题


网络中有两台计算机s和t,现在每秒钟要从s传输大小为F的数据到t。该网络中一共有N太计算机,其中一些计算机之间连有一条单向的通信电缆,每条通信电缆都有对应的一秒内传输的最大数据量。此外,每条电缆还有对应的传输费用,即单位传输费用为d的通信电缆传输大小为x的数据,需要费用为dx。请问传输数据的最小费用。

问题可以转换为一个有向图(计算机为各顶点,传输电缆为边)。每条边有其容量c(e)和费用d(e)。问题可以转换为在保证从s向t有大小为F的流的情况下,使得总费用最小。就是最小费用流问题(最大流情况下每条边添加费用F,求最小值)。

贪心增广,参与网络中的反向边费用应该是原边费用的相反数。需要注意最小费用流不能使用Dijkstra算法因为有负权边。可以使用Bellman-Ford算法

Bellman-Ford模板:

#define N 1000
#define INF 100000000

struct Edge
{
    int from,to,cap,flow,cost;
};
struct MCMF
{
    int n,m,s,t;
    vectoredges;
    vectorG
;
    int inq
;//是否在队列中
    int d
;//Bellman-Ford
    int p
;//上一条弧
    int a
;//可改进量

    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;

        queueq;
        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;
    }
};

可以通过数学归纳法证明算法为最小费用流(即证明残余网络中没有负圈),证明过程可以详见MIT讲义

特殊情况

 

  • 对于流量任意
    如果需要计算包含负权边的图中流量任意但费用最小的流。可以根据最小流算法中h[i+1](v)>=h[i](v)的性质,在h[i](t)<0时进行增广。
  • 对于费用为负
    存在负权边需要用Bellman-Ford算法。存在负圈可以利用算法找到负圈并在负圈上尽量增广。通过变形避免负权边的算法(每次增广时如边数相等,通过对所有边费用加上合适常数将边转成非负数)只适用部分情况。

参考

原文标题:图论:最小费用流与Bellman-Ford算法|落絮飞雁的个人网站
授权协议:创作共用 署名-非商业性使用 2.5 中国大陆
除注明外,本站文章均为原创;转载时请保留上述链接。

发表评论

textsms
account_circle
email

落絮飞雁的个人网站

图论:最小费用流与Bellman-Ford算法
最小传输费用问题 网络中有两台计算机s和t,现在每秒钟要从s传输大小为F的数据到t。该网络中一共有N太计算机,其中一些计算机之间连有一条单向的通信电缆,每条通信电缆都有对应的一秒…
扫描二维码继续阅读
2016-04-15