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

最小费用最大流的意思就是，在流量相同的情况下，我们找出最小费用的最大流。
方法是每次寻找一条最小花费的路，这个寻找我们用最短路算法spfa，这里的最短路修改成最小花费，权值的名称变了而已。
找到之后单位花费之和，也就是d[t]，###### 到终点的最小代价 * 该流的流量 ##### 累加起来就可以了。
需要注意的是，反边的费用应该设置成原本花费的相反数。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

const int maxn=5e4+100;
const int INF=0x3f3f3f3f;

int cost=0,n,m,s,t,ecnt=0;

struct Edge {
    int v,w,cost,next;
};

struct Node {
    int u,ecnt;
};

Node pre[maxn/10];
Edge edge[2*maxn];
int head[maxn/10];
bool inque[maxn/10];
int dis[maxn/10];

void addEdge(int u,int v,int w,int c)
{
    edge[ecnt].v=v;
    edge[ecnt].w=w;
    edge[ecnt].cost=c;
    edge[ecnt].next=head[u];
    head[u]=ecnt++;
}

bool spfa()
{
    memset(dis,INF,sizeof(dis));
    memset(inque,0,sizeof(inque));
    memset(pre,-1,sizeof(pre));
    inque[s]=true;
    queue<int> q;
    dis[s]=0;
    q.push(s);
    while (!q.empty()) {
        int u=q.front();
        inque[u]=false;
        q.pop();
        for (int i=head[u];i+1;i=edge[i].next) {
            int v=edge[i].v;
            int c=edge[i].cost;
            if (edge[i].w>0&&dis[v]>dis[u]+c) {
                dis[v]=dis[u]+c;
                pre[v].u=u;
                pre[v].ecnt=i;
                if (!inque[v]) {
                    q.push(v);
                    inque[v]=true;
                }
            }
        }
    }
    if (dis[t]==INF) {
        return false;
    }
    return true;
}

int MCMF()
{
    int ans=0;
    while (spfa()) {
        int mi=INF;
        for (int i=t;i!=s;i=pre[i].u) {
            mi=min(mi,edge[pre[i].ecnt].w);
        }
        for (int i=t;i!=s;i=pre[i].u) {
            edge[pre[i].ecnt].w-=mi;
            edge[pre[i].ecnt^1].w+=mi;
        }
        ans+=mi;
        cost+=mi*dis[t];
    }
    return ans;
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    memset(head,-1,sizeof(head));
    memset(edge,0,sizeof(edge));
    int u,v,w,c;
    while (m--) {
        scanf("%d%d%d%d",&u,&v,&w,&c);
        addEdge(u,v,w,c);
        addEdge(v,u,0,-c);
    }
    printf("%d ",MCMF());
    printf("%d
",cost);
    return 0;
}