费用流

原理

见《进阶指南》第449页。
模板题

#include <iostream>
#include <cstring>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 5010, M = 50010;
struct edge {
    int to, next, c, w; // w：单位费用
};
edge e[2 * M];
int idx, head[N];
int n, m, s, t, max_flow, res;
int dis[N], flow[N], eid[N];
bool mark[N];

void add_edge (int u, int v, int c, int w) {
    e[idx].c = c;
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;

    e[idx].c = 0;
    e[idx].w = -w;
    e[idx].to = u;
    e[idx].next = head[v];
    head[v] = idx ++;
}
bool spfa () {
    memset(mark, 0, sizeof(mark));
    memset(dis, 0x3f, sizeof(dis));
    
    queue<int> q;
    dis[s] = 0;
    flow[s] = inf;
    q.push(s);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        mark[cur] = false;
        for (int i = head[cur]; i != -1; i = e[i].next) {
            int to = e[i].to, c = e[i].c, w = e[i].w;
            if (c == 0) continue;
            if (dis[cur] + w < dis[to]) {
                dis[to] = dis[cur] + w;
                flow[to] = min(flow[cur], c);
                eid[to] = i;
                if (mark[to] == false) {
                    q.push(to);
                    mark[to] = true;
                }
            }
        }
    }
    return dis[t] != inf;
}
void update () {
    int cur = t;
    while (cur != s) {
        int i = eid[cur];
        e[i].c -= flow[t];
        e[i ^ 1].c += flow[t];
        cur = e[i ^ 1].to;
    }
    max_flow += flow[t];
    res += dis[t] * flow[t];
}

int main () {
    memset(head, -1, sizeof(head));
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1, u, v, c, w; i <= m; ++ i) {
        scanf("%d%d%d%d", &u, &v, &c, &w);
        add_edge(u, v, c, w);
    }

    while (spfa() == true) update();
    printf("%d %d", max_flow, res);
    return 0;
}
# 费用流

# 原理

# 模板题

费用流

原理

模板题
