模板题

洛谷P3381 【模板】最小费用最大流

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 5005
#define M 100005
using namespace std;
int n, m, s, t, tot = -1, max_flow = 0, min_cost = 0;
int st[N], dis[N], cur[N], vis[N], pre[N], min_flow[N], q[N * 200];
struct node
{
    int to, last, val, f/*flow*/;
}w[M];
void add(int u, int v, int f, int ww)
{
    w[++tot].to = v;
    w[tot].last = st[u];
    w[tot].f = f;
    w[tot].val = ww;
    st[u] = tot;
}
bool spfa()
{
    int l = 0, r = 1;
    q[r] = s;
    memset(dis, 0x3f, sizeof dis);
    memset(min_flow, 0x3f, sizeof min_flow);
    memset(cur, -1, sizeof cur);
    memset(pre, -1, sizeof pre);
    dis[s] = 0;
    vis[s] = 1;
    while (l != r)
    {
        int u = q[++l];
        for (int i = st[u]; i != -1; i = w[i].last)
        {
            if (w[i].f > 0 && dis[w[i].to] > dis[u] + w[i].val)
            {
                dis[w[i].to] = dis[u] + w[i].val;
                pre[w[i].to] = u;
                cur[w[i].to] = i;
                min_flow[w[i].to] = min(min_flow[u], w[i].f);
                if (!vis[w[i].to])
                {
                    vis[w[i].to] = 1;
                    q[++r] = w[i].to;
                }
            }
        }
        vis[u] = 0;
    }
    return cur[t] != -1;
}
void dinic()
{
    while (spfa())
    {
        int flow = min_flow[t];
        max_flow += flow;
        min_cost += flow * dis[t];
        for (int i = t; i != s; i = pre[i])
            w[cur[i]].f -= flow, w[cur[i] ^ 1].f += flow;
    }
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(st, -1, sizeof st);
    for (int i = 1; i <= m; i++)
    {
        int u, v, ww, f;
        scanf("%d%d%d%d", &u, &v, &f, &ww);
        add(u, v, f, ww);
        add(v, u, 0, -ww);
    }
    dinic();
    printf("%d %d\n", max_flow, min_cost);
    return 0;
}

最小费用最大流

原文：https://www.cnblogs.com/featherZHY/p/11334391.html