# P1559 运动员最佳匹配问题

# 解法

通过读到 计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大 这么一句话，你应该很快就能想到这是有关于二分图最大权完美匹配的问题。

那么二分图最大权完美匹配相较于二分图完美匹配来说，是边权有了权值，不是单纯的为了让配对数更多（或者是搜索出配对数最多的配对方法等）。

其他题解对于 KM 算法已经讲解的非常透彻了，我这里就稍微说说连边。

看到这个题目，你会发现两个人之间都有关系，即 A 对 B 有一个值， B 对 A 也有一个值，而在以往做的时候可能只会出现 A 对 B 有一个值，因为 A 对 B 与 B 对 A 的值都是给定的，那么我们 合并这两个值，也就是题目中的 $p[i][j] \times q[j][i]$ ，那么 A 与 B 的连边的权值也就确定了，那么就可以跑 KM 算法啦。

Code

	/*
	1. 设置最大期望值
	2. 利用匈牙利算法找增广路
	3. 找到增广路，匹配成功，退出
	4. 找不到，最小程度降低男生期望，提升女生期望
	5. 继续回到 (2) 开始重复


	val1 [N]/val2 [N] 分别记录 U 集与 V 集点的点权（匹配期望值）

	vis1 [N]/vis2 [N] 分别记录每次寻找增广路过程中 U 集与 V 集点的访问情况

	match [N] 记录最终 U 集内点匹配到的在 V 集内点的编号

	slack [N] 记录匹配过程中，U 集内任意点能够选择 V 集内任意点作为匹配对象所需要降低 val（期望值）的最小值
	*/

	#include<iostream>
	#include<algorithm>
	#include<cstring>
	#include<cstdio>
	#include<cmath>
	#include<map>
	#include<queue>
	#define int long long
	using namespace std;
	const int INF=0x3f3f3f3f3f;
	const int N=550;
	int n,m,match[N],pri[N];
	bool vis2[N];
	long long a[N][N];
	long long fav[N][N],val1[N],val2[N],sla[N];

	void bfs(int k){
	int x,y=0,z=0;
	memset(pri,0,sizeof(pri));
	memset(sla,INF,sizeof(sla));
	match[0]=k;
	do{
	int d=INF;
	x=match[y];
	vis2[y]=true;
	for(int i=1;i<=n;i++){
	if(vis2[i]){
	continue;
	}
	if(sla[i]>val1[x]+val2[i]-fav[x][i]){
	sla[i]=val1[x]+val2[i]-fav[x][i];
	pri[i]=y;
	}
	if(sla[i]<d){
	d=sla[i];
	z=i;
	}
	}
	for(int i=0;i<=n;i++){
	if(vis2[i]){
	val1[match[i]]-=d;val2[i]+=d;
	}else{
	sla[i]-=d;
	}
	}
	y=z;
	}while(match[y]);
	while(y){
	match[y]=match[pri[y]];
	y=pri[y];
	}
	}
	int KM(){
	memset(match,0,sizeof(match));
	memset(val1,0,sizeof(val1));
	memset(val2,0,sizeof(val2));
	for(int i=1;i<=n;i++){
	memset(vis2,false,sizeof(vis2));
	bfs(i);
	}
	int res=0;
	for(int i=1;i<=n;i++){
	res+=fav[match[i]][i];
	}
	return res;
	}
	signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
	cin>>a[i][j];
	}
	}
	for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
	int k;
	cin>>k;
	a[j][i]*=k;// 记得这里的 j 与 i 是反的，因为枚举是正着枚举的
	}
	}
	for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
	fav[i][j]=max(fav[i][j],a[i][j]);
	}
	}
	cout<<KM()<<endl;
	}