算法：MinCostMaxFlow(SPFA)
问题：最小费用最大流问题
输入：带有w(容量)和c(费用)的有向图
输出：最小费用、最大流
备注：不要吝啬内存

#include<bits/stdc++.h>
#define INF 0x3fffffff
#define maxn 100
#define maxm 10000
using namespace std;

int pre[maxn],dis[maxn];
int vis[maxn],cnt[maxn];
int n,m,src,tar;

int head[maxn],tot;
struct Edge {
    int from,to;
    int w,c,nxt;
} e[maxm];

void adde(int f,int t,int w,int c){
    e[tot]=Edge{f,t,w,c,head[f]};
    head[f]=tot++;
    e[tot]=Edge{t,f,0,-c,head[t]};
    head[t]=tot++;
}

int mincost,maxflow;
int spfa() {
    for(int i=0; i<n; i++)
        dis[i]=INF;
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));

    queue<int>p;
    p.push(src);
    dis[src]=0;
    vis[src]=1;
    cnt[src]=1;
    while(!p.empty()) {
        int u=p.front(); p.pop();
        vis[u]=0;
        for(int i=head[u]; ~i; i=e[i].nxt) {
            int v=e[i].to;
            if(e[i].w&&dis[v]>dis[u]+e[i].c) {
                dis[v]=dis[u]+e[i].c;
                pre[v]=i;
                if(!vis[v]) {
                    p.push(v);
                    vis[v]=1;
                    cnt[v]++;
                    if(cnt[v]>n) return 0;
                }
            }
        }
    }
    return dis[tar]<INF;
}

void MCMF() {
    maxflow=0;
    mincost=0;
    while(spfa()) {
        int f=INF;
        for(int i=tar;i!=src;i=e[pre[i]].from)
            f=min(f,e[pre[i]].w);
        assert(f>0);
        assert(dis[tar]<INF);
        for(int i=tar;i!=src;i=e[pre[i]].from) {
            e[pre[i]^1].w+=f;
            e[pre[i]].w-=f;
        }

        maxflow+=f;
        mincost+=dis[tar]*f;
    }
}