作者：0And1Story
链接：https://zhuanlan.zhihu.com/p/720469052
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#define rep(i, l, r) for (int i = l; i <= r; ++i)

const long long inf = INT_MAX;

struct Edge {
    int v, nxt, f, w;
};

const int N = 1e3;
const int M = 1e6;
int n, m, s, t, s2;
int cur[N];
long long dis[N];
bool vis[N];
Edge E[M << 1];
int head[N];
int sz = 1;
int cnt;
long long sum;
int cn[N];

int l[N], c[N], v[N];

void add_edge(int u, int v, int f, int w) {
    E[++sz] = {v, head[u], f, w};
    head[u] = sz;
}

void add_flow(int u, int v, int f, int w) {
    add_edge(u, v, f, w), add_edge(v, u, 0, -w);
}

bool spfa() {
    deque<int> q;
    rep(i, 1, cnt) dis[i] = inf, cur[i] = head[i], vis[i] = false;
    q.push_front(t), dis[t] = 0, vis[t] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        vis[u] = 0;
        for (int i = head[u]; i; i = E[i].nxt) {
            auto& [v, nxt, f, w] = E[i];
            if (E[i ^ 1].f && dis[v] > dis[u] + E[i ^ 1].w) {
                dis[v] = dis[u] + E[i ^ 1].w;
                if (vis[v]) continue;
                if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
                else q.push_back(v);
                vis[v] = 1;
            }
        }
    }
    return dis[s] != inf;
}

long long cost;

long long dfs(int u, long long flow) {
    if (u == t || !flow) return flow;
    vis[u] = 1;
    long long rest = flow;
    for (int& i = cur[u]; i; i = E[i].nxt) {
        auto& [v, nxt, f, w] = E[i];
        if (vis[v] || dis[u] != dis[v] + w || !f) continue;
        long long x = dfs(v, min(rest, (long long)f));
        if (x) E[i].f -= x, E[i ^ 1].f += x, rest -= x, cost += w * x;
        if (!rest) break;
    }
    vis[u] = 0;
    return flow - rest;
}

long long MinCostFlow() {
    long long res = 0, flow;
    while (spfa()) {
        while ((flow = dfs(s, inf))) res += flow;
    }
    return res;
}

void init() {
    sum = 0;
    sz = 1;
    cost = 0;
    memset(head, 0, sizeof(int) * (cnt + 1));
    memset(cn, 0, sizeof(int) * (m + 1));
}

answer.code:4:1: error: extended character 。 is not valid in an identifier
    4 | 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
      | ^
answer.code:4:1: error: extended character 。 is not valid in an identifier
answer.code:1:1: error: ‘作者：0And1Story’ does not name a type
    1 | 作者：0And1Story
      | ^~~~~~~~~~~~~~~~
answer.code: In function ‘bool spfa()’:
answer.code:39:5: error: ‘deque’ was not declared in this scope
   39 |     deque<int> q;
      |     ^~~~~
answer.code:39:11: error: expected primary-expression before ‘int’
   39 |     deque<int> q;
      |           ^~~
answer.code:40:29: error: ‘inf’ was not declared in this scope; did you mean ‘int’?
   40 |     rep(i, 1, cnt) dis[i] = inf, cur[i] = head[i], vis[i] = false;
      |                             ^~~
      |                             int
answer.code:41:5: error: ‘q’ was not declared in this scope
   41 |     q.push_front(t), dis[t] = 0, vis[t] = 1;
      |     ^
answer.code:57:22: error: ‘inf’ was not declared in this scope; did you mean ‘int’?
   57 |     return dis[s] != inf;
      |                      ^~~
      |                      int
answer.code: In function ‘long long int dfs(int, long long int)’:
answer.code:69:30: error: ‘min’ was not declared in this scope
   69 |         long long x = dfs(v, min(rest, (long long)f));
      |                              ^~~
answer.code: In function ‘long long int MinCostFlow()’:
answer.code:80:31: error: ‘inf’ was not declared in this scope; did you mean ‘int’?
   80 |         while ((flow = dfs(s, inf))) res += flow;
      |                               ^~~
      |                               int
answer.code: In function ‘void init()’:
answer.code:89:5: error: ‘memset’ was not declared in this scope
   89 |     memset(head, 0, sizeof(int) * (cnt + 1));
      |     ^~~~~~
answer.code:1:1: note: ‘memset’ is defined in header ‘<cstring>’; did you forget to ‘#include <cstring>’?
  +++ |+#include <cstring>
    1 | 作者：0And1Story