最小费用最大流模板

const int inf = 0x3f3f3f3f;
const int maxn = 1000+10;

int n;     //n个顶点
struct Edge{ int from, to, cap, flow, cost; };
vector<Edge> edges;
vector<int> G[maxn];
int inque[maxn];   //SPFA 需要用到
int d[maxn];       //当前点到源点的最短路
int p[maxn];       //连接当前点的弧
int a[maxn];       //可改进量

void init()
{
    for(int i=0; i<=n; i++) G[i].clear();
    edges.clear();
}

void add_edge(int from, int to, int cap, int cost)
{
    edges.push_back((Edge){from, to, cap, 0, cost});
    edges.push_back((Edge){to, from, 0, 0, -cost});
    int m = edges.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
}

bool spfa(int s, int t, int &flow, long long &cost)
{
    for(int i=0; i<=n; i++) d[i] = inf;
    memset(inque, 0, sizeof(inque));
    d[s] = 0; inque[s]=1; p[s] = 0; a[s] = inf;
    queue<int> que;
    que.push(s);
    while(!que.empty()){
        int u = que.front(); que.pop();
        inque[u] = 0;
        for(int i=0; i<G[u].size(); i++){
            Edge e = edges[G[u][i]];
            if(e.cap>e.flow && d[e.to]>d[u]+e.cost){
                d[e.to] = d[u] + e.cost;
                if(!inque[e.to]) que.push(e.to), inque[e.to]=1;
                p[e.to] = G[u][i];    //e.to连接的边是G[u][i]
                a[e.to] = min(a[u], e.cap-e.flow);   //更新可改进量
            }
        }
    }
    if(d[t] == inf) return false;
    flow += a[t];
    cost += (long long)a[t] * (long long)d[t];
    for(int u=t; u!=s; u=edges[p[u]].from)
    {
        edges[p[u]].flow += a[t];
        edges[p[u]^1].flow -= a[t];
    }
    return true;
}
int MCMF(int s, int t, long long &cost)
{
    int flow = 0; cost = 0;
    while(spfa(s, t, flow, cost));
    return flow;
}