解题(求赞)

#include <bits/stdc++.h>
using namespace
std;
#define rep(i, u) for (int i = fir[u]; i; i = e[i].nxt)
int read()
{
int x = 0, f = 1; char ch = getchar
();
while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar
(); }
while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar
(); }
return
x * f;
}
const int inf = 50000000
;
int T, n, ans, a[73][73], b[73][73
];
struct Vector
{
int
x, y;
Vector
() {}
Vector(int xx, int
yy) { x = xx, y = yy; }
friend Vector operator - (Vector a, Vector b) { return Vector
(a.x - b.x, a.y - b.y); }
friend int operator * (Vector a, Vector b) { return
a.x * b.y - a.y * b.x; }
};
struct Graph
{
int g[73][73], lx[73], ly[73], sla[73], match[73
];
bool visx[73], visy[73
];
void build(int wx, int wy)
{
for (int i = 1
; i <= n; i++)
for (int j = 1
; j <= n; j++)
g[i][j] = -(wx * a[i][j] + wy * b[i][j]);
}
bool dfs(int u)
{
visx[u] =
true
;
for (int v = 1; v <= n; v++) if
(!visy[v])
{
int
t = lx[u] + ly[v] - g[u][v];
if
(!t)
{
visy[v] =
1
;
if (!match[v] || dfs
(match[v]))
{
match[v] = u;
return true
;
}
}
else sla[v] = min
(sla[v], t);
}
return false
;
}
Vector km()
{
memset(lx, 0, sizeof
lx);
memset(ly, 0, sizeof
ly);
memset(match, 0, sizeof
match);
for (int i = 1
; i <= n; i++)
for (int j = 1
; j <= n; j++)
lx[i] =
max
(lx[i], g[i][j]);
for (int i = 1
; i <= n; i++)
{
memset(sla, 63, sizeof
sla);
while (true
)
{
memset(visx, 0, sizeof
visx);
memset(visy, 0, sizeof
visy);
if (dfs(i)) break
;
int
d = inf;
for (int i = 1
; i <= n; i++)
if (!visy[i]) d = min
(d, sla[i]);
for (int i = 1
; i <= n; i++)
if
(visx[i]) lx[i] -= d;
for (int i = 1
; i <= n; i++)
if
(visy[i]) ly[i] += d;
else
sla[i] -= d;
}
}
Vector re(0, 0)
;
for (int i = 1
; i <= n; i++)
re.x += a[match[i]][i], re.y += b[match[i]][i];
return
re;
}
} g;
void solve(Vector A, Vector B)
{
g.
build
(A.y - B.y, B.x - A.x);
Vector C = g.
km
();
ans =
min
(ans, C.x * C.y);
if ((B - A) * (C - A) >= 0) return
;
solve(A, C), solve
(C, B);
}
int main()
{
T =
read
();
while
(T--)
{
n =
read
();
for (int i = 1
; i <= n; i++)
for (int j = 1
; j <= n; j++)
a[i][j] =
read
();
for (int i = 1
; i <= n; i++)
for (int j = 1
; j <= n; j++)
b[i][j] =
read
();
g.
build(1, 0
);
Vector A = g.
km
();
g.
build(0, 1
);
Vector B = g.
km
();
ans =
min
(A.x * A.y, B.x * B.y);
solve
(A, B);
printf("%d\n"
, ans);
}
return 0
;
}