最小费用最大流 理解

时间：2022-11-22 04:32:27

首先，要想理解这个算法，必须得理解最大流的求法，关于最大流呢，就是一个不断循环找可行路，不断增加流量的过程。。。
     其次，求出最小费用。这个费用，就是一定的流量通过一条特定的路径，从源点到达汇点，所花费的费用，那我们不妨把这个一定的流量设为1，这样的话，所花费的费用就是该特定路径上的每一条边的费用的和，要求最小费用，可以理解为求经过路径上的每一个条边的费用和最小，这样就可以转化为求定点到求终点的最小路径问题。我们可以用bellman-ford算法，spfa，都行，反正你开心就好。。。
      我们把最小费用最大流看成是同时求最大流和最小费用，那我们在求最大流的代码基础之上，增加一个判断条件d[e.to]>d[u]+e.cost（见代码56行），以及更新最小费用d[e.to]=d[u]+e.cost;（63行）。
      在每一次的循环增加流量的时候，因为每单位流量通过一个特定路径的费用一定，那我们在一次循环之后用最小费用乘以该次循环增加到流量再加到总流量上就更新了最小费用`//最小费用路算法

struct Edge
{
int to, from, flow, cap, cost;
Edge(int i, int j, int k, int l, int m):to(i), from(j), flow(k), cap(l), cost(m);
}

struct EdmondsKarp()
{
int n, m;
vector edges;
vector Gra[n];
int inq[n];
int d[n]; // bellman-ford算法-用来求最小费用
int flow_sum[n]; //保存流量之和
int pre[n]; //保存路径

void Init()     //vector使用初始化
{
    for(int i=0;i<n;++i)
    {
        Gra[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));
    int size=edges.size()
    Gra[from].push_back(m-2);
    Gra[to].push_back(m-1);
}

int BellMan(int src,int dest, int &cost)
{
    int sum=0;
    for(int i=0;i<n;++i)
        d[i]=INF;
    memset(inq,0, sizeof(inq));
    d[s]=0;
    inq[s]=0;
    a[s]=INF;
    queue<int> inq;
    inq.push(src);
    while(!inq.empty())
    {
        int temp=inq.top();
        inq.pop();
        for(int i=0;i<Gra[temp].size();++i)
        {
            Edge e=Gra[temp][i];
            if(d[e.to]>d[u]+e.cost&&e.cap>e.flow)
            {
                flow_sum[e.to]=std::min(flow_sum[e.from], e.cap-e.flow);
                pre[e.to]=Gra[temp][i];
                d[e.to]=d[u]+e.cost;
                if(!inq[e.to])
                {
                    inq[e.to]=1;
                    Q.push(e.to);
                }
            }
        }
    }
    if(d[t]==INF)
        return false;
    sum+=flow_sum[dest];    //增加到流量
    cost+=(long long)d[t]*(long long)a[t];   //计算增加的费用
    for(int u=dest;u!=src;u=edges[pre[u]].from)
    {
        edges[pre[u]].flow+=flow_sum[src];
        edges[pre[u]^1].flow-=flow_sum[dest];//反向边的作用，使能量守恒，本来寻找最大流就是一个动态的过程，给一个反悔的机会，
        //还有一个技巧，之前的加边的时候有一个技巧使得，0和1是反向边，2和3是反向边。。。那0^1=1,1^1=0;2^1=3;3^1=2;这里的^是异或位运算。对于一条边，进行异或运算就可以得到其反向边，（详见：《算法竞赛入门经典》第二版P368
    }
    return ture;
}

int MinCostMacxFlow(int src,int t,long &cost)
{
    int flow=0;cost=0;
    while(BellManFodrd());
    return flow;
}

}`

以上代码来自《算法竞赛入门经典》
标签：

相关文章