最小费用最大流算法及题集

待我称王封你为后i 2022-08-13 05:59 257阅读 0赞

貌似网上最小费用最大流的讲解的不多。

所谓最小费用最大流：就是在保证从源点 S 到汇点 T 的流量最大的前提下，使费用最小

这就在原先最大流问题的网络中，给每天边上新加上了费用，求得不在是最大流，而是在最大流的前提的下最小费用。

求解最大流的时候，我们不断的在残余网络上不断的贪心增广而得到最大流，现在边上多了费用，而求得正好是最小的费用，那么我们是不是每次可以沿着最短路增广呢，每条边的费用看作是权值，这样求得的必然是最小费用最大流。

首先[hdoj 1533][][ ][hdoj 1533]

题意：给出一个m\*n的图，然后让你从 m 到 H 的的最小花费。

建图方法：

s 到所有 m 点连接：容量1，费用0

所有 H 点到 t 连接：容量1，费用0

其他点奇偶建图，容量inf，费用1

下面给一个最小费用最大流的模板，一些注意的地方陆续总结到这里。

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <cstring>
    #include <queue>
    #include <string>
    #include <map>
    using namespace std;
    #define Del(a,b) memset(a,b,sizeof(a))
    const int inf = 0x3f3f3f3f;
    const int N = 220;
    struct Node
    {
        int from,to,cap,flow,cost;
    };
    vector<Node> e;
    vector<int> v[N];
    int vis[N],dis[N];
    int p[N],a[N];  //p保存father，a保存cap
    void Clear(int x)
    {
        for(int i=0;i<=x;i++)
            v[i].clear();
        e.clear();
    }
    void add_Node(int from,int to,int cap,int cost)
    {
        e.push_back((Node){from,to,cap,0,cost});
        e.push_back((Node){to,from,0,0,-cost});
        int len = e.size()-1;
        v[to].push_back(len);
        v[from].push_back(len-1);
    }
    bool BellmanFord(int s,int t,int& flow,int& cost)
    {
        Del(dis,inf);
        Del(vis,0);
        dis[s] = 0;
        vis[s] = 1;
        p[s] = 0;
        a[s] = inf;
        queue<int> q;
        q.push(s);
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            vis[u] = 0;
            for(int i=0; i<v[u].size(); i++)
            {
                Node& g = e[v[u][i]];
                if(g.cap>g.flow && dis[g.to] > dis[u]+g.cost)
                {
                    dis[g.to] = dis[u] + g.cost;
                    p[g.to] = v[u][i];  //保存前驱
                    a[g.to] = min(a[u],g.cap-g.flow);
                    if(!vis[g.to])
                    {
                        q.push(g.to);
                        vis[g.to]=1;
                    }
    
                }
            }
        }
        if(dis[t] == inf)
            return false;
        flow += a[t];
        cost += dis[t]*a[t];
        int u = t;
        while(u!=s)
        {
            e[p[u]].flow += a[t];
            e[p[u]^1].flow -= a[t];
            u = e[p[u]].from;
        }
        return true;
    }
    int Min_Cost(int s,int t)
    {
        int flow=0,cost = 0;
        while(BellmanFord(s,t,flow,cost));
        return cost;
    }

[hdoj 1533]: http://acm.hdu.edu.cn/showproblem.php?pid=1533