最小费用最大流

#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <functional>
#include <map>
#include <set>
#include <stack>
#define FT(a, b) memset(a, b, sizeof(a))
#define FAT(a) memset(a, 0, sizeof(a))
using namespace std;
typedef long long ll;
const int M = 4e4 + 100;
const int N = 1e3 + 100;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int n, m, k;
int h[N], e[M], ne[M], w[M], idx, f[M], flow[M], pre[M], last[M];
int d[N];
char gap[N][N];
int vis[M];
int s = 0, t = 1;
int min_cost, max_flow;
void add(int a, int b, int c, int d)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, f[idx] = d, h[a] = idx++;
}
bool spfa()
{
    FAT(vis);
    FT(d, INF);
    FT(flow, INF);
    queue<int> q;
    q.push(s);
    d[s] = 0;
    vis[s] = 1;
    pre[t] = -1;
    while (!q.empty())
    {
        int a = q.front();
        q.pop();
        vis[a] = 0;
        for (int i = h[a]; ~i; i = ne[i])
        {
            int j = e[i];
            if (f[i] && d[j] > d[a] + w[i])
            {
                d[j] = d[a] + w[i];
                flow[j] = min(f[i], flow[a]);
                pre[j] = a;
                last[j] = i;
                if (!vis[j])
                {
                    vis[j] = 1;
                    q.push(j);
                }
            }
        }
    }
    return pre[t] != -1;
}
void MCMF()
{
    while (spfa())
    {
        max_flow += flow[t];
        min_cost += flow[t] * d[t];
        int now = t;
        while (now != s)
        {
            f[last[now]] -= flow[t];
            f[last[now] ^ 1] += flow[t];
            now = pre[now];
        }
    }
}