_rqy's Blog

一只猫猫,想成为天才少女数学家!

0%

BZOJ3996 [TJOI2015] 线性代数

Description

给定nnn*n的矩阵BB1n1*n的矩阵CC。求一个1N1*N的01矩阵AA使得(ABC)AT(AB-C)A^T最大。ATA^TAA的转置。n500n\leqslant500,所有输入为不超过10001000的非负整数。

Solution

(AB)i=j=1nAjBj,i(ABC)i=(j=1nAjBj,i)Ci(ABC)AT=i=1nAi(j=1nAjBj,i)AiCi=i,j=1nAiAjBi,ji=1nAiCi\begin{aligned} (AB)_i&=\sum_{j=1}^n A_jB_{j,i}\\ (AB-C)_i&=\left(\sum_{j=1}^n A_jB_{j,i}\right) - C_i\\ (AB-C)A^T&=\sum_{i=1}^n A_i\left(\sum_{j=1}^nA_jB_{j,i}\right)-A_iC_i\\ &=\sum_{i,j=1\dots n} A_iA_jB_{i,j} -\sum_{i=1}^nA_iC_i \end{aligned}

观察最后一个式子,可以看成:

nn个物品,第i,ji,j两个物品同时选会获得Bi,jB_{i,j}的收益;选第ii个物品会付出CiC_i的代价;求最大净收益。

最小割即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <algorithm>
#include <cstdio>
#include <cstring>
const int N = 500;
const int NN = 500000;
const int M = 3000050;
int pre[NN], nxt[M], to[M], ret[M], cnt;
int dis[NN], que[NN];
bool BFS(int S, int T) {
int hd = 0, tl = 0;
memset(dis, -1, sizeof dis);
for (dis[que[tl++] = S] = 0; hd < tl; ++hd)
for (int i = pre[que[hd]]; ~i; i = nxt[i])
if (ret[i] && !~dis[to[i]]) dis[que[tl++] = to[i]] = dis[que[hd]] + 1;
return dis[T] != -1;
}
int DFS(int x, int T, int maxf) {
if (!maxf) return 0;
if (x == T) return maxf;
int ans = 0;
for (int i = pre[x]; ~i; i = nxt[i])
if (ret[i] && dis[to[i]] == dis[x] + 1) {
int t = DFS(to[i], T, std::min(maxf - ans, ret[i]));
ret[i] -= t; ret[i ^ 1] += t;
ans += t;
}
if (ans < maxf) dis[x] = -1;
return ans;
}
int solve(int S, int T) {
int ans = 0;
while (BFS(S, T)) ans += DFS(S, T, 1000000000);
return ans;
}
inline void addEdge(int x, int y, int c) {
nxt[cnt] = pre[x];
ret[cnt] = c;
to[pre[x] = cnt++] = y;
nxt[cnt] = pre[y];
ret[cnt] = 0;
to[pre[y] = cnt++] = x;
}
int main() {
int n;
scanf("%d", &n);
memset(pre, -1, sizeof pre);
int S = n * (n + 1), T = S + 1;
int ans = 0;
for (int i = 0; i < n; ++i)
for (int j = 0, v; j < n; ++j) {
scanf("%d", &v);
ans += v;
int t = (i + 1) * n + j;
addEdge(t, T, v);
addEdge(i, t, 1000000000);
addEdge(j, t, 1000000000);
}
for (int i = 0, v; i < n; ++i) {
scanf("%d", &v);
addEdge(S, i, v);
}
printf("%d\n", ans - solve(S, T));
return 0;
}