题解

我原来根本不会KM

更新每个节点增加的最小值的时候，要忽略那个方访问过的右节点！！！

然后就和最小乘积生成树一样了

代码

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <queue>

#include <cmath>

#define enter putchar('\n')

#define space putchar(' ')

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define pii pair<int,int>

#define eps 1e-7

#define MAXN 100005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

typedef vector<int> poly;

template<class T>

void read(T &res) {

	res = 0;char c = getchar();T f = 1;

	while(c < '0' || c > '9') {

		if(c == '-') f = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		res = res * 10 + c - '0';

		c = getchar();

	}

	res *= f;

}

template<class T>

void out(T x) {

	if(x < 0) {putchar('-');x = -x;}

	if(x >= 10) {

		out(x / 10);

	}

	putchar('0' + x % 10);

}

int T;

int N,ans;

int A[75][75],B[75][75],C[75][75];

bool vis_l[75],vis_r[75];

int slack[75],matk[75],ex_l[75],ex_r[75];

bool match(int u) {

	vis_l[u] = 1;

	for(int v = 1 ; v <= N ; ++v) {

		if(vis_r[v]) continue;

		int gap = C[u][v] - (ex_l[u] + ex_r[v]);

		if(gap == 0) {

			vis_r[v] = 1;

			if(matk[v] == -1 || match(matk[v])) {

				matk[v] = u;

				return 1;

			}

		}

		else slack[v] = min(slack[v],gap);

	}

	return 0;

}

pii KM() {

	for(int i = 1 ; i <= N ; ++i) matk[i] = -1;

	for(int i = 1 ; i <= N ; ++i) {

		ex_l[i] = 1000000000;ex_r[i] = 0;

		for(int j = 1 ; j <= N ; ++j) {

			if(C[i][j] < ex_l[i]) ex_l[i] = C[i][j];

		}

	}

	for(int i = 1 ; i <= N ; ++i) {

		for(int j = 1 ; j <= N ; ++j) slack[j] = 1000000000;

		while(1) {

			memset(vis_l,0,sizeof(vis_l));

			memset(vis_r,0,sizeof(vis_r));

			if(match(i)) break;

			int d = 1000000000;

			for(int j = 1 ; j <= N ; ++j) if(!vis_r[j]) d = min(d,slack[j]);

			for(int j = 1 ; j <= N ; ++j) {

				if(vis_l[j]) ex_l[j] += d;

				if(vis_r[j]) ex_r[j] -= d;

				else slack[j] -= d;

			}

		}

	}

	int rA = 0,rB = 0;

	for(int i = 1 ; i <= N  ; ++i) {

		rA += A[matk[i]][i];

		rB += B[matk[i]][i];

	}

	return mp(rA,rB);

}

void Init() {

	read(N);

	for(int i = 1 ; i <= N ; ++i) {

		for(int j = 1 ; j <= N ; ++j) {

			read(A[i][j]);

		}

	}

	for(int i = 1 ; i <= N ; ++i) {

		for(int j = 1 ; j <= N ; ++j) {

			read(B[i][j]);

		}

	}

}

void Calc(pii S,pii T) {

	for(int i = 1 ; i <= N ; ++i) {

		for(int j = 1 ; j <= N ; ++j) {

			C[i][j] = (S.se - T.se) * A[i][j] + (T.fi - S.fi) * B[i][j];

		}

	}

	pii M = KM();

	ans = min(ans,M.fi * M.se);

	if((T.fi - M.fi) * (S.se - M.se) - (S.fi - M.fi) * (T.se - M.se) <= 0) return;

	Calc(S,M);Calc(M,T);

}

void Solve() {

	ans = 0x7fffffff;

	memcpy(C,A,sizeof(C));

	pii S = KM();

	ans = min(ans,S.fi * S.se);

	memcpy(C,B,sizeof(C));

	pii T = KM();

	ans = min(ans,T.fi * T.se);

	if(S != T) Calc(S,T);

	out(ans);enter;

}

int main() {

#ifdef ivorysi

	freopen("f1.in","r",stdin);

#endif

	read(T);

	while(T--) {

		Init();

		Solve();

	}

	return 0;

}