最小费用最大流和Edmonds-Karp算法

为流量网络中的每一条边赋予一个单位流量代价，在求最大流的基础上求最小代价的问题称为最小费用最大流问题（一般也称为费用流问题）。

求最大流的Edmonds-Karp算法通过广度优先搜索寻找增广路。
求费用流时，将广搜改为SPFA，求一条总单位开销最小的增广路，这样就可以保证方案总开销最小的同时流量最大。

queue<int> Q;
bool inQ[MaxN];
int dis[MaxN], limit[MaxN], from[MaxN];
node* fromedge[MaxN];
bool bfs() {
    while (!Q.empty())
        Q.pop();
    valfill(inQ + 1, inQ + n + 1, false);
    valfill(dis + 1, dis + n + 1, infinity);
    valfill(limit + 1, limit + n + 1, infinity);
    Q.push(s);
    inQ[s] = true;
    dis[s] = 0;
    from[s] = 0;
    fromedge[s] = nullptr;
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop(); inQ[u] = false;
        for (node* p = h[u]; p != nullptr; p = p->next) {
            int v = p->v, flow = p->flow, cost = p->cost;
            if (flow > 0) {
                if (dis[v] > dis[u] + cost) {
                    dis[v] = dis[u] + cost;
                    limit[v] = min(limit[u], flow);
                    from[v] = u;
                    fromedge[v] = p;
                    if (!inQ[v]) {
                        inQ[v] = true;
                        Q.push(v);
                    }
                }
            }
        }
    }
    if (dis[t] == infinity)
        return false;
    else
        return true;
}

搜索时应对于每一个节点记录上一个节点的编号和指向上一条边的指针，以便于更新边上的剩余流量和总开销。

int maxflow, mincost;
void update() {
    maxflow += limit[t];
    mincost += limit[t] * dis[t];
    int v = t;
    while (v != s) {
        node* p = fromedge[v];
        p->flow -= limit[t];
        p->rev->flow += limit[t];
        v = from[v];
    }
}

以下是求费用流的Edmonds-Karp算法的主流程：

void edmondsKarp(){
    while (bfs())
        update();
}

时间复杂度：广搜\(O(nm)\)，总体\(O(nm^2)\)

以下是版子

constexpr int infinity = 1e8;
constexpr int MaxN = 5000 + 10, MaxM = 50000 + 10;

int n, m;
int s, t;

struct node {
    int v, flow, cost;
    node* next;
    node* rev;
};

node* h[MaxN];
node mem[2 * MaxM], *memtop = mem;
#define ALLOCATE (++memtop)

void addedge(int u, int v, int flow, int cost) {
    node* p1 = ALLOCATE;
    p1->v = v;
    p1->flow = flow;
    p1->cost = cost;
    p1->next = h[u];
    h[u] = p1;
    node* p2 = ALLOCATE;
    p2->v = u;
    p2->flow = 0;
    p2->cost = -cost;
    p2->next = h[v];
    h[v] = p2;
    p1->rev = p2;
    p2->rev = p1;
}

template<typename Iterator, typename ValType>
void valfill(Iterator begin, Iterator end, ValType val) {
    while (begin != end) {
        *begin = val;
        begin++;
    }
}

queue<int> Q;
bool inQ[MaxN];
int dis[MaxN], limit[MaxN], from[MaxN];
node* fromedge[MaxN];
bool bfs() {
    while (!Q.empty())
        Q.pop();
    valfill(inQ + 1, inQ + n + 1, false);
    valfill(dis + 1, dis + n + 1, infinity);
    valfill(limit + 1, limit + n + 1, infinity);
    Q.push(s);
    inQ[s] = true;
    dis[s] = 0;
    from[s] = 0;
    fromedge[s] = nullptr;
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop(); inQ[u] = false;
        for (node* p = h[u]; p != nullptr; p = p->next) {
            int v = p->v, flow = p->flow, cost = p->cost;
            if (flow > 0) {
                if (dis[v] > dis[u] + cost) {
                    dis[v] = dis[u] + cost;
                    limit[v] = min(limit[u], flow);
                    from[v] = u;
                    fromedge[v] = p;
                    if (!inQ[v]) {
                        inQ[v] = true;
                        Q.push(v);
                    }
                }
            }
        }
    }
    if (dis[t] == infinity)
        return false;
    else
        return true;
}

int maxflow, mincost;
void update() {
    maxflow += limit[t];
    mincost += limit[t] * dis[t];
    int v = t;
    while (v != s) {
        node* p = fromedge[v];
        p->flow -= limit[t];
        p->rev->flow += limit[t];
        v = from[v];
    }
}

void edmondsKarp() {
    while (bfs())
        update();
}