最小费用最大流

说明

出处:《算法竞赛入门经典(第二版)》

使用方法

  1. MCMF::init(n) n个点
  2. MCMF::adde(u,v,cap,cost); 加边
  3. long long minCost, maxFlow;
  4. maxFlow = MCMF::MincostMaxflow(st, ed, minCost); 执行完的结果maxFlow为最大流 minCost为最小费用

Tips

  • 需要保证初始网络中没有负权圈,不过可以有负权边
  • 求最大费用最大流:将所有边的费用都加个负号,最后结果再加回来一个负号即可
  • n个点的下标可以为0~n-1也可以为1~n
  • 拆点的话要把顶点数加倍

示例

  1. POJ 2195 Going Home
  2. UVa 1658 Admiral
  3. HDU 3488 Tour

模版

const int Vmax=2005; //需要拆点的话记得加倍
namespace MCMF{
    struct Edge{
        int from,to,cap,flow,cost;
        Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){}
    };

    int n,m;
    vector<Edge>edges;
    vector<int>G[Vmax];
    int inq[Vmax];  //是否在队列中
    int d[Vmax];    //Bellman-Ford
    int p[Vmax];    //上一条弧
    int a[Vmax];    //可改进量

    void init(int _Vsz){
        n=_Vsz;
        for(int i=0;i<=n;i++) G[i].clear();
        edges.clear();
    }

    void adde(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 SPFA(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);
                    if(!inq[e.to]){
                        q.push(e.to);
                        inq[e.to]=1;
                    }
                }
            }
        }
        if(d[t]==INF) return false; //s-t 不联通,失败退出
        flow+=a[t];
        cost+=(long long)d[t]*(long long)a[t];
        for(int u=t;u!=s;u=edges[p[u]].from){
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
        }
        return true;
    }

    int MincostMaxflow(int s,int t,long long& cost){
        int flow=0;
        cost=0;
        while(SPFA(s, t, flow, cost));
        return flow;
    }
}

results matching ""

    No results matching ""