萌新求助

#include <bits/stdc++.h>
using namespace std;
const int N = 206, M = 1e5 + 6, inf = 0x3f3f3f3f;
int n, m, S, T, s, s_, t, d[N], now[N], pre[N], ans;
int Head[N], Edge[M], Leng[M], Cost[M], Next[M], tot = 1;
bitset<N> v;

inline void add(int x, int y, int z, int w) {
    Edge[++tot] = y;
    Leng[tot] = z;
    Cost[tot] = w;
    Next[tot] = Head[x];
    Head[x] = tot;
    Edge[++tot] = x;
    Leng[tot] = 0;
    Cost[tot] = -w;
    Next[tot] = Head[y];
    Head[y] = tot;
}

inline void ins(int x, int y, int l, int r, int w) {
    add(x, y, r - l, w);
    d[x] -= l;
    d[y] += l;
}

inline bool spfa() {
    v.reset();
    memset(d, 0x3f, sizeof(d));
    queue<int> q;
    q.push(S);
    v[S] = 1;
    d[S] = 0;
    now[S] = m;
    while (q.size()) {
        int x = q.front();
        q.pop();
        v[x] = 0;
        for (int i = Head[x]; i; i = Next[i]) {
            int y = Edge[i], z = Leng[i], w = Cost[i];
            if (!z || d[y] <= d[x] + w) continue;
            d[y] = d[x] + w;
            now[y] = min(now[x], z);
            pre[y] = i;
            if (!v[y]) {
                q.push(y);
                v[y] = 1;
            }
        }
    }
    return d[T] != inf;
}

inline void upd() {
    ans += d[T] * now[T];
    int x = T;
    while (x != S) {
        int i = pre[x];
        Leng[i] -= now[T];
        Leng[i^1] += now[T];
        x = Edge[i^1];
    }
}

int main() {
    cin >> n >> m;
    s = n * 2 + 1, s_ = s + 1, t = s_ + 1;
    S = t + 1, T = S + 1;
    ins(s, s_, m, m, 0);
    for (int i = 1; i <= n; i++) {
        ins(s_, i, 0, m, 0);
        ins(i + n, t, 0, m, 0);
        int x;
        scanf("%d", &x);
        ins(i, i + n, x, x, 0);
    }
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            int x;
            scanf("%d", &x);
            if (~x) ins(i + n, j, 0, m, x);
        }
//  ins(t, s, 0, m, 0);
    for (int i = 1; i <= t; i++) {
        if (d[i] > 0) add(S, i, d[i], 0);
        else if (d[i] < 0) add(i, T, -d[i], 0);
    }
    while (spfa()) upd();
    cout << ans << endl;
    return 0;
}