#include<iostream>
using namespace std;
int **p;
int **q;
int *w;//存放配对的女运动员的编号
int bestsum=-1;
int n;
void swap(int &a,int &b)
{
int t=a;
a=b;
b=t;
}
void Backtrack(int level)
{
int csum=0;
if(level>=n)
{
for(int i=0;i<n;i++)
{
csum+=p[i][w[i]]*q[w[i]][i];
}
if(csum>bestsum)
{
bestsum=csum;
}
}
else
{
for(int j=level;j<n;j++)
{
swap(w[level],w[j]);
Backtrack(level+1);
swap(w[level],w[j]);
}
}
}
int main()
{
int i,row,col;
cin>>n;
p=new int *[n];
q=new int *[n];
w=new int [n];
for(i = 0;i < n;i++)
w[i] = i;
for(i=0;i<n;i++)
{
p[i]=new int[n];
q[i]=new int[n];
}
for(row=0;row<n;row++)
{
for(col=0;col<n;col++)
{
cin>>p[row][col];
}
}
for(row=0;row<n;row++)
{
for(col=0;col<n;col++)
{
cin>>q[row][col];
}
}
Backtrack(0);
cout<<bestsum<<endl;
return 0;
}
评论9
最新资源