根据题目，我们很快能看出来，这是一个带权的二分图匹配问题。
二分图匹配，我们可以跑**最大流
**
而带上权值呢？ 就可以跑最小费用最大流233。
啥? 不是求最大吗？ 怎么可以跑最小费用？
其实是可以的。 对于最基础的最小费用最大流：每次求一条可以增广的最短路。然后增广。
而我们根据这个题，我们需要求得是最大，也就是最长路。
我们就可以，将权值取负数，然后用SPFA跑最短路。
这样问题就迎刃而解了。（dij好像也可以，只不过我太vegetable，不会
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
struct node
{
int point;
int flow;
int val;
int nxt;
};
node line[100000];//前项星
int head[100],tail=-1;
void add(int x,int y,int f,int v)
{
line[++tail].point=y;
line[tail].flow=f;
line[tail].val=v;
line[tail].nxt=head[x];
head[x]=tail;
}//加边
int male[21][21];
int famale[21][21];//读入的数据，看数组名就可以了，不需要再解释了233
int max_cost;//最大的费用，就是答案
int flow[100],last[100],dis[100];//last是把每个点更新的边的编号
int pre[100];
bool inque[100];//SPFA找最短的增广路所需要的数组
bool SPFA(int begin,int end)
{
queue<int>q;
memset(dis,10,sizeof(dis));
memset(flow,0,sizeof(flow));
memset(inque,0,sizeof(inque));
memset(pre,0,sizeof(pre));//初始化
dis[begin]=0;pre[begin]=0;flow[begin]=0x7fffffff;//源点流量无限
inque[begin]=true;q.push(begin);
while(!q.empty())
{
int pas=q.front(); q.pop();
inque[pas]=false;
for(int i=head[pas];i!=-1;i=line[i].nxt)//遍历
if(line[i].flow>0&&dis[line[i].point]>dis[pas]+line[i].val)//一定要判断是否可以增广
{
dis[line[i].point]=dis[pas]+line[i].val;//最短路
last[line[i].point]=i;pre[line[i].point]=pas;//储存边的编号，以便后来更改
flow[line[i].point]=min(flow[pas],line[i].flow);//流量更新,其实是不需要的，因为我们现在在做二分图匹配嘛
if(!inque[line[i].point])
{
inque[line[i].point]=true;
q.push(line[i].point);
}
}
}
if(!pre[end]) return false;//汇点是否到达
return true;
}
void EK(int begin,int end)
{
while(SPFA(begin,end))
{
int pas=end;
max_cost+=dis[end]*flow[end]*-1;//因为我们取负存嘛，所以要倒回来
while(pas!=begin)//从汇点到源点进行增广
{
line[last[pas]].flow-=flow[end];
line[last[pas]^1].flow+=flow[end];//last就用上了
pas=pre[pas];
}
}
return ;
}
int main()
{
int n;
scanf("%d",&n);
int len=n;
for(int i=0;i<=(len<<1)+1;i++) head[i]=-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&male[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&famale[i][j]);//初始化与输入
for(int i=1;i<=n;i++)//建图，0为源点，n*2+1为汇点
{
add(0,i,1,0),add(i,0,0,0);
add(len+i,(len<<1)+1,1,0),add((len<<1)+1,len+i,0,0);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
add(i,len+j,1,male[i][j]*famale[j][i]*-1),add(len+j,i,0,male[i][j]*famale[j][i]);//记住取负
EK(0,(len<<1)+1);
printf("%d",max_cost);
}