「BZOJ3996」[TJOI2015]线性代数

Description

给出一个 N×NN \times N 的矩阵 B\mathbf{B} 和一个 1×N1 \times N 的矩阵 C\mathbf{C}。求出一个 1×N1 \times N0101 矩阵 A\mathbf{A},使得
D=(ABC)ATD=(\mathbf{A}\mathbf{B}-\mathbf{C})\mathbf{A}^T 最大。其中 AT\mathbf{A}^TA\mathbf{A} 的转置。输出 DD

Input

第一行输入一个整数 NN,接下来 NN 行输入 B\mathbf{B} 矩阵, 第 ii 行第 jj 个数字代表 BijB_{ij}.

接下来一行输入 NN 个整数,代表矩阵 C\mathbf{C}。矩阵 BB 和矩阵 CC 中每个数字都是不超过 10001000 的非负整数。

Output

输出最大的 DD

Sample Input

1
2
3
4
5
3
1 2 1
3 1 0
1 2 3
2 3 7

Sample Output

1
2

HINT

对于所有的数据,1N5001 \leq N \leq 500

Solution

假如AB=CAB=C,那么Ci,j=kAi,kBk,jC_{i,j}=\sum_k A_{i,k}B_{k,j}
回到题目:
(AB)1,i=k=1nAkBk,i(AB)_{1,i}=\sum_{k=1}^nA_{k}B_{k,i}
(ABC)1,i=(k=1nAkBk,i)Ci(AB-C)_{1,i}=(\sum_{k=1}^nA_{k}B_{k,i})-C_i
((ABC)AT)1,1=i=1n(ABC)1,iAi=i=1n((k=1nAkBk,i)Ci)Ai((AB-C)A^{T})_{1,1}=\sum_{i=1}^n(AB-C)_{1,i}A_i=\sum_{i=1}^n((\sum_{k=1}^nA_{k}B_{k,i})-C_i)A_i
继续化简:
((ABC)AT)1,1=i=1nk=1nAiAkBk,ii=1nCiAi((AB-C)A^{T})_{1,1}=\sum_{i=1}^n\sum_{k=1}^n A_iA_kB_{k,i}-\sum_{i=1}^n C_i A_i
相当于如果iikk同时选择,那么可以获得Bk,i+Bi,kB_{k,i}+B_{i,k},CiC_{i}表示选择ii的代价。

建边方法

SS(i,j)(i,j)连一条容量为Bi,jB_{i,j}的边
(i,j)(i,j)iijj分别连一条容量为infinf的边
iitt,连容量为CiC_{i}的边。
ans=i=1nj=1nBi,jans=\sum_{i=1}^n\sum_{j=1}^nB_{i,j}
那么答案就是ansmaxflowans-maxflow

原理

要么是断开SS(i,j)(i,j)的边,要么是同时断了(i,t)(i,t)(j,t)(j,t)的边。
如果割掉SS(i,j)(i,j)的边,意味着iijj没有全选,所以减去Bi,jB_{i,j}
如果割掉ii且割掉jj,意味着(i,j)(i,j)iijj的边都没有被割掉,因为割掉就不是最小割了,因为iijjtt的割的权值正好就是他们的代价。

代码

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 510, M = N * N * 4;
int n;
int b[N][N], c[N];
int s, t;
struct Edge {
int u, v, nxt, f;
}e[M * 2];
int head[N * N], en = 1;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = z;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0;
}
int d[N * N];
bool bfs() {
for(int i = 1; i <= t; ++i) d[i] = 0;
d[s] = 1;
queue<int>q;
q.push(s);
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f){
int y = e[i].v;
if(!d[y]) {
d[y] = d[x] + 1;
if(y == t) return 1;
q.push(y);
}
}
}
return 0;
}
int dinic(int x, int flow) {
if(x == t) return flow;
int k, rest = flow;
for(int i = head[x]; i && rest; i = e[i].nxt) if(d[e[i].v] == d[x] + 1 && e[i].f) {
k = dinic(e[i].v, min(e[i].f, rest));
e[i].f -= k;
e[i ^ 1].f += k;
rest -= k;
}
if(rest == flow) d[x] = 0;
return flow- rest;
}
const int inf = 1e9;
int main() {
n = read();
s = n * n + n + 1;
t = n * n + n + 2;
int ans = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
b[i][j] = read();
int x = (i - 1) * n + j;
addedge(s, x, b[i][j]);
addedge(x, n * n + i, inf); //只有i和j都不割,才会割s->b[i][j]
addedge(x, n * n + j, inf);
ans += b[i][j];
}
}
for(int i = 1; i <= n; ++i) {
c[i] = read();
addedge(n * n + i, t, c[i]);
}
int res = 0, y;
while(bfs()) while(y = dinic(s, inf)) res += y;
writeln(ans - res);
return 0;
}