就是求$D = A \times B \times A^T - C \times A^T$
展开也就是$$D = \sum_{i, j} A_i * A_j * B_{i, j} - \sum_{i} C_i * A_i$$
其中$Ai = 0 \ or \ 1$
转化成最小割模型，就是一堆东西，选了$i$号物品要支付费用$C_i$，同时选$i$和$j$两个物品可以获得$B_{i, j}$的收益
于是非常简单啦，建图什么的直接看程序好了！
/**************************************************************
Problem: 3996
User: rausen
Language: C++
Result: Accepted
Time:476 ms
Memory:51612 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
const int N = * ;
const int M = N << ;
const int inf = 1e9; struct edge {
int next, to, f;
edge() {}
edge(int _n, int _t, int _f) : next(_n), to(_t), f(_f) {}
} e[M]; int n, ans, S, T;
int first[N], tot = ;
int d[N], q[N]; inline int read(); inline void Add_Edges(int x, int y, int f) {
e[++tot] = edge(first[x], y, f), first[x] = tot;
e[++tot] = edge(first[y], x, ), first[y] = tot;
} #define y e[x].to
#define p q[l]
bool bfs() {
int l, r, x;
memset(d, -, sizeof(d));
d[q[] = S] = ;
for (l = r = ; l != r + ; ++l)
for (x = first[p]; x; x = e[x].next)
if (!~d[y] && e[x].f) {
d[q[++r] = y] = d[p] + ;
if (y == T) return ;
}
return ;
}
#undef p int dfs(int p, int lim) {
if (p == T || !lim) return lim;
int x, tmp, rest = lim;
for (x = first[p]; x && rest; x = e[x].next)
if (d[y] == d[p] + && ((tmp = min(e[x].f, rest)) > )) {
rest -= (tmp = dfs(y, tmp));
e[x].f -= tmp, e[x ^ ].f += tmp;
if (!rest) return lim;
}
if (rest) d[p] = -;
return lim - rest;
}
#undef y int Dinic() {
int res = ;
while (bfs())
res += dfs(S, inf);
return res;
} int main() {
int i, j, x, now;
n = now = read(), S = n * n + n + , T = S + ;
for (i = ; i <= n; ++i)
for (j = ; j <= n; ++j) {
x = read(), ++now;
Add_Edges(i, now, inf), Add_Edges(j, now, inf);
Add_Edges(now, T, x);
ans += x;
}
for (i = ; i <= n; ++i) Add_Edges(S, i, read());
printf("%d\n", ans - Dinic());
return ;
} inline int read() {
static int x;
static char ch;
x = , ch = getchar();
while (ch < '' || '' < ch)
ch = getchar();
while ('' <= ch && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x;
}