最小费用最大流spfa

时间：2022-02-14 23:28:56
#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

const int maxn = , INF = 0x7fffffff;

int head[maxn], d[maxn], vis[maxn], p[maxn], f[maxn];

int n, m, s, t;

int flow, value;

struct node{

    int u, v, c, f, w, next;

}Node[maxn];

void add(int u, int v, int c, int f, int w, int i)

{

    Node[i].u = u;

    Node[i].v = v;

    Node[i].c = c;

    Node[i].f = f;

    Node[i].w = w;

    Node[i].next = head[u];

    head[u] = i;

}

int spfa()

{

    queue<int> Q;

    mem(vis,);

    mem(p,-);

    for(int i=; i<=n; i++) d[i] = INF;

    d[s] = ;

    Q.push(s);

    vis[s] = ;

    p[s] = ; f[s] = INF;

    while(!Q.empty())

    {

        int u = Q.front(); Q.pop();

        vis[u] = ;

        for(int i=head[u]; i!=-; i=Node[i].next)

        {

            node e = Node[i];

            if(d[e.v] > d[u] + e.w && e.c > e.f)

            {

                d[e.v] = d[u] + e.w;

                p[e.v] = i;

                f[e.v] = min(f[u], e.c - e.f);

                if(!vis[e.v])

                {

                    Q.push(e.v);

                    vis[e.v] = ;

                }

            }

        }

    }

    if(p[t] == -) return ;

    flow += f[t]; value += f[t] * d[t];

    for(int i=t; i!=s; i=Node[p[i]].u)

    {

        Node[p[i]].f += f[t];

        Node[p[i]^].f -= f[t];

    }

    return ;

}

void max_flow()

{

    while(spfa());

    printf("%d %d\n",flow,value);

}

int main()

{

    mem(head,-);

    cin>> n >> m >> s >> t;

    int cnt = ;

    flow = , value = ;

    for(int i=; i<m; i++)

    {

        int u, v, c, w;

        cin>> u >> v >> c >> w;

        add(u,v,c,,w,cnt++);

        add(v,u,,,-w,cnt++);

    }

    max_flow();

    return ;

}

相关文章