标签: 最小费用流

最小费用最大流的一种算法:SPFA版Edmons-Karp

最小费用最大流的一种算法:SPFA版Edmons-Karp

这里不介绍算法,只提供模板代码。所有代码基于【P3381】【模板】最小费用最大流 – 洛谷一题。

SPFA版Edmons-Karp

// Code by KSkun, 2017/12
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>

struct io {
    char buf[1 << 26], *s;

    io() {
        //freopen("p3381.in", "r", stdin);
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline int read() {
        register int res = 0;
        while(*s < '0' || *s > '9') s++;
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res;
    }
} ip;

#define read ip.read

const int MAXN = 100005;
const int INF = 1e9;

struct Edge {
    int to, cap, cost, rev;
    Edge(int to, int cap, int cost, int rev): to(to), cap(cap), cost(cost), rev(rev) {}
};

std::vector<Edge> vec[MAXN];
std::queue<int> que;
int f[MAXN];
int pre[MAXN], pree[MAXN], dis[MAXN];
bool inque[MAXN];

inline void addedge(int u, int v, int cap, int cost) {
    vec[u].push_back(Edge(v, cap, cost, vec[v].size()));
    vec[v].push_back(Edge(u, 0, -cost, vec[u].size() - 1));
}

// SPFA Min Cost Flow

int flow = 0, cost = 0;

inline void min_cost_flow(int s, int t) {
    for(;;) {
        memset(f, 0, sizeof f);
        memset(dis, 0x3f, sizeof dis);
        memset(inque, 0, sizeof inque);
        while(!que.empty()) que.pop();
        que.push(s);
        dis[s] = 0;
        inque[s] = true;
        f[s] = INF;
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            inque[u] = false; 
            for(int i = 0; i < vec[u].size(); i++) {
                int v = vec[u][i].to;
                if(vec[u][i].cap > 0 && dis[v] > dis[u] + vec[u][i].cost) {
                    pre[v] = u;
                    pree[v] = i;
                    f[v] = std::min(vec[u][i].cap, f[u]);
                    dis[v] = dis[u] + vec[u][i].cost;
                    if(!inque[v]) {
                        que.push(v);
                        inque[v] = true;
                    }
                }
            }
        }
        if(f[t] == 0) break;
        for(int u = t; u != s; u = pre[u]) {
            vec[pre[u]][pree[u]].cap -= f[t];
            vec[u][vec[pre[u]][pree[u]].rev].cap += f[t];
        }
        flow += f[t];
        cost += f[t] * dis[t];
    }
}

int n, m, s, t, ut, vt, wt, ct;

int main() {
    n = read();
    m = read();
    s = read();
    t = read();
    for(int i = 0; i < m; i++) {
        ut = read();
        vt = read();
        wt = read();
        ct = read();
        addedge(ut, vt, wt, ct);
    }
    min_cost_flow(s, t);
    printf("%d %d", flow, cost);
    return 0;
}