题面

解法

\(ans\) = 所有的收益 - \(i\)属于\(S\)割的(雇佣\(i\)的代价) - 不能同时雇佣\(i,j\)的带价(\(i\)属于\(S\)割,\(j\)属于T割) - 不雇佣\(i\)所造成的带价也就是\(i\)所有的贡献(\(i\)属于\(T\)割)

那么建图也就出来了：\(S\rightarrow i\)连\(a_i\)，\(i\rightarrow j\)连\(E_{i,j}\)，\(i\rightarrow T\)连\(i\)的所有贡献

答案就是所有的贡献和减去最小割。

注意要加当前弧优化

代码

#include 
    
     #define N 2010using namespace std;template 
     
       void read(node &x) {    x = 0; int f = 1; char c = getchar();    while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}    while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;}struct Edge {    int next, num, c;} e[N * N];int s, t, cnt, a[N], sum[N], l[N], cur[N], v[N][N];void add(int x, int y, int c) {    e[++cnt] = (Edge) {e[x].next, y, c};    e[x].next = cnt;}void Add(int x, int y, int c) {    add(x, y, c), add(y, x, 0);}bool bfs(int s) {    for (int i = 1; i <= t; i++) l[i] = -1;    queue 
      
        q; q.push(s);    while (!q.empty()) {        int x = q.front(); q.pop();        for (int p = e[x].next; p; p = e[p].next) {            int k = e[p].num, c = e[p].c;            if (c && l[k] == -1)                l[k] = l[x] + 1, q.push(k);        }    }    return l[t] != -1;}int dfs(int x, int lim) {    if (x == t) return lim;    int used = 0;    for (int p = cur[x]; p; p = e[p].next) {        int k = e[p].num, c = e[p].c;        if (l[k] == l[x] + 1 && c) {            int w = dfs(k, min(c, lim - used));            e[p].c -= w, e[p ^ 1].c += w;            if (e[p].c) cur[x] = p;            used += w;            if (used == lim) return used;        }    }    if (!used) l[x] = -1;    return used;}int dinic() {    int ret = 0;    while (bfs(s)) {        for (int i = s; i <= t; i++)            cur[i] = e[i].next;        ret += dfs(s, INT_MAX);    }    return ret;}int main() {    int n, ans = 0; read(n);    for (int i = 1; i <= n; i++) read(a[i]);    for (int i = 1; i <= n; i++)        for (int j = 1; j <= n; j++)            read(v[i][j]), sum[i] += v[i][j], ans += v[i][j];    s = 0, t = cnt = n + 1;    if (cnt % 2 == 0) cnt++;    for (int i = 1; i <= n; i++)        Add(s, i, a[i]), Add(i, t, sum[i]);    for (int i = 1; i <= n; i++)        for (int j = 1; j <= n; j++)            Add(i, j, v[i][j] * 2);    cout << ans - dinic() << "\n";    return 0;}