Description：

给一个二分图和 $i$ 与 $j$ 匹配的两个权值 $x[i][j]$ 和 $y[i][j]$ ，求一组匹配，最小化： $$ \sum_{i=1}^na[i][match[i]]\times \sum_{i=1}^nb[i][match[i]] $$ $1\leqslant n\leqslant 70$

Solution：

不难看出和最小乘积生成树本质是一个东西，只是把 $Kruskal$ 换成了 $KM$ 而已。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n;

#define MAXN 75

typedef long long ll;

ll x[MAXN][MAXN],y[MAXN][MAXN],w[MAXN][MAXN];

#define INFLL 0x3f3f3f3f3f3f3f3f

struct point

{

	ll x,y;

};

point operator - (point a,point b){return (point){a.x - b.x,a.y - b.y};}

ll operator * (point a,point b){return a.x * b.y - a.y * b.x;}

point ans;

point min(point a,point b)

{

	if(a.x * a.y < b.x * b.y)return a;

	else return b;

}

int match[MAXN];

bool va[MAXN],vb[MAXN];

ll la[MAXN],lb[MAXN],delta;

bool find(int i)

{

	va[i] = true;

	for(int j = 1;j <= n;++j)

	{

		if(!vb[j])

		{

			if(la[i] + lb[j] == w[i][j])

			{

				vb[j] = true;

				if(match[j] == -1 || find(match[j]))

				{

					match[j] = i;

					return true;

				}

			}

			else

			{

				delta = min(delta,la[i] + lb[j] - w[i][j]);

			}

		}

	}

	return false;

}

point KM()

{

	for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)w[i][j] *= -1;

	memset(match,-1,sizeof(match));

	for(int i = 1;i <= n;++i)

	{

		la[i] = -INFLL;lb[i] = 0;

		for(int j = 1;j <= n;++j)la[i] = max(la[i],w[i][j]);

	}

	for(int k = 1;k <= n;++k)

	{

		while(true)

		{

			memset(va,false,sizeof(va));

			memset(vb,false,sizeof(vb));

			delta = INFLL;

			if(find(k))break;

			for(int i = 1;i <= n;++i)

			{

				if(va[i])la[i] -= delta;

				if(vb[i])lb[i] += delta;

			}

		}

	}

	point ans;ans.x = 0;ans.y = 0;

	for(int i = 1;i <= n;++i)

	{

		ans.x += x[match[i]][i];

		ans.y += y[match[i]][i];

	}/*cout << " : " << endl;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= n;++j)

		{

			cout << w[i][j] << " ";

		}

		cout << endl;

	}

	for(int i = 1;i <= n;++i)cout << match[i] << " " << i << endl;*/

	return ans;

}

void solve(point A,point B)

{

	ans = min(ans,min(A,B));

	for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)w[i][j] = (B.x - A.x) * y[i][j] - (B.y - A.y) * x[i][j];

	point C = KM();

	if((B - A) * (C - A) >= 0)return;

	solve(A,C);solve(C,B);

	return;

}

void work()

{

	ans.x = INFLL;ans.y = INFLL;

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)x[i][j] = rd();

	for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)y[i][j] = rd();

	for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)w[i][j] = x[i][j];

	point A = KM();

	for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)w[i][j] = y[i][j];

	point B = KM();

	solve(A,B);

	cout << ans.x * ans.y << endl;

	return;

}

int main()

{

	int testcases = rd();

	while(testcases--)work();

	return 0;

}