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

· · 题解

为什么不点个赞呢（雾）

如果您连网络最大流都不会写那么请出门左转P3376

费用流板子题，没什么题意解释

何为费用流？

费用流就是网络流的一种

那网络流又是啥？

不知道

网络流(network-flows)是一种类比水流的解决问题方法，与线性规划密切相关。网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。

什么鬼东西，百度百科不可信

简单来说，网络流就相当于一个供水系统（雾），有个自来水公司，以及若干水管、储水塔，还有你家

你每天都要用水，水就得从自来水厂流过来，但是水管直径有限，能流过水的多少是一定的 （如果有谁觉得只要时间够就可以流很多那我就拿着刀子冲上去了），你最多可以接收到的水量就称为网络最大流

所以这个东西大致就变成了这样

这就很好理解了

但是，当你满怀雄心壮志想要AC P3376 【模板】网络最大流的时候，却发现自来水厂要收费了

（自来水厂：我们每天辛辛苦苦给高速行驶的水管换水，付点水费不是很正常吗？）

于是他就要收费了，每流过去一单位的水，就要收费f_i元

这就从最大流变成了费用流

费用流怎么做？

费用流全名叫做最小费用最大流

所以如果再用BFS去找增广路……

23333

我们换个角度去想

BFS不行不就是因为它只能找增广路而不是花费最小的增广路吗？

那么花费最小的增广路怎么找呢？

我们只需要在BFS上动点手脚……

就可以把它改造成……

对，你没看错，就是SPFA

因为NOI2019没有卡SPFA所以他又复活了

Why SPFA?

众所周知，单源最短路是在保证图联通的情况下求出的

那不就好了吗？

图联通就意味着有增广路

Dijkstra：为什么不选我？？？

众所周知，dij不能处理负边权……

然而这题毒瘤数据里似乎有负的……

虽然处理一下可以AC，但SPFA它不香吗？

Code

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 5001;
const int MAXM = 50001;
int n, m, s, t, edge_sum = 1;
int maxflow, mincost;
int dis[MAXN], head[MAXN], incf[MAXN], pre[MAXN];//dis表示最短路，incf表示当前增广路上最小流量，pre表示前驱
bool vis[MAXN];
struct Edge {
    int next, to, dis, flow;
}edge[MAXM << 1];
inline void addedge(int from, int to, int flow, int dis) {
    edge[++edge_sum].next = head[from];
    edge[edge_sum].to = to;
    edge[edge_sum].dis = dis;
    edge[edge_sum].flow = flow;
    head[from] = edge_sum;
}
inline bool spfa() {//关于SPFA，他诈尸了
    queue <int> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    q.push(s);
    dis[s] = 0;
    vis[s] = 1;
    incf[s] = 1 << 30;
    while(!q.empty()) {
        int u = q.front();
        vis[u] = 0;
        q.pop();
        for(register int i = head[u]; i; i = edge[i].next) {
            if(!edge[i].flow) continue;//没有剩余流量
            int v = edge[i].to;
            if(dis[v] > dis[u] + edge[i].dis) {
                dis[v] = dis[u] + edge[i].dis;
                incf[v] = min(incf[u], edge[i].flow);//更新incf
                pre[v] = i;
                if(!vis[v]) vis[v] = 1, q.push(v);
            }
        }
    }
    if(dis[t] == 1061109567) return 0;
    return 1;
}
inline void MCMF() {
    while(spfa()) {//如果有增广路
        int x = t;
        maxflow += incf[t];
        mincost += dis[t] * incf[t];
        int i;
        while(x != s) {//遍历这条增广路，正向边减流反向边加流
            i = pre[x];
            edge[i].flow -= incf[t];
            edge[i^1].flow += incf[t];
            x = edge[i^1].to;
        }
    }
}
signed main() {
    scanf("%d%d%d%d", &n,&m,&s,&t);
    for(register int u,v,w,x,i = 1; i <= m; ++i) {
        scanf("%d%d%d%d",&u,&v,&w,&x);
        addedge(u,v,w,x);
        addedge(v,u,0,-x);//反向边费用为-f[i]
    }
    MCMF();//最小费用最大流
    printf("%d %d\n",maxflow,mincost);
    return 0;
}

Accpeted!