题解 P3381 【【模板】最小费用最大流】

Xie_BR · 2019-08-06 19:46:29 · 题解

同志们，同胞们：

费用流，费用六，最小费用最大流

其实这是一道模板题 首先，我们需要考虑的是在费用的增广路上赋负值，所以我们需要用到的bfs大发应该是spfa（dij不能走负边）
于是，我们很愿意在最大流的木板上，加上有关费用的判断，便可以很轻松得A了这道题！！！

#include<bits/stdc++.h>
#define int long long
#define MK 200100
using namespace std;
int n,m,S,T;
int ans = 0;
int cost = 0;
int f[MK];
int dep[MK];
int id[MK];
int mn[MK];

struct node
{
    int next,to,v,w;
}e[MK*2];

int ei = 1,h[MK];

void add(int x,int y,int v,int w)
{
    ei++;
    e[ei].to = y;
    e[ei].v = v;
    e[ei].w = w;
    e[ei].next = h[x];
    h[x] = ei;
}

int dis[MK],u[MK];

int spfa()
{
    queue<int>qu;
    memset(dis,0x3f,sizeof(dis));
    memset(f,0,sizeof(f));
    memset(mn,0x3f,sizeof(mn));
    memset(u,0,sizeof(u));
    memset(id,0,sizeof(id));
    qu.push(S);
    dis[S] = 0;
    f[S] = 0;
    while(!qu.empty())
    {
        int f1 = qu.front();
        qu.pop();
        u[f1] = 0;
        for(int i=h[f1];i;i=e[i].next)
        {
            int to = e[i].to;
            if(e[i].v==0 || dis[to]<=dis[f1]+e[i].w)
            {
                continue;
            }
            dis[to] = dis[f1]+e[i].w;
            f[to] = f1;
            id[to] = i;
            mn[to] = min(mn[f1],e[i].v);
            if(u[to]==0)
            {
                u[to] = 1;
                qu.push(to);
            }
        }
    }
    return dis[T]!=dis[0];
}

int update()
{
    int next = T;
    while(f[next]!=0)
    {
        e[id[next]].v -= mn[T];
        e[id[next]^1].v += mn[T];
        next = f[next];
    }
    return mn[T];
}

void EK()
{
    while(spfa())
    {
        int k = 0;
        k += update();
        ans += k;
        cost += k*dis[T];
    }
}

signed main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&S,&T);
    while(m--)
    {
        int x,y,v,w;
        scanf("%lld%lld%lld%lld",&x,&y,&v,&w);
        add(x,y,v,w);
        add(y,x,0,-w);
    }
    EK();
    printf("%lld %lld\n",ans,cost);
    return 0;
}

嘻嘻嘻，可能有些水，但是简单明了，还请大佬指教！！！