运动员最佳配问题，羽毛球队有男女运动员各N人给定两个N *N矩阵P和Q。
P[I][J]是男运动员I和女运动员J配对组成混合双打的竞赛优势；Q[I][J]是女运
动员I 和男运动员J配合的竞赛优势.由于配合和心理状态等各种因素影响，P[I][J]
不一定等于Q[J][I]。
设计一个算法计算男女运动员最佳配对法，使各组男女双方竞赛优势乘积
的总和达到最大。
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;
vector<int> Re; 青年人网提示全局变量,Re用来记录配对情况
vector<vector<int>> P;
vector<vector<int>> Q;
class Queen
{
friend int PairUp(int);
private:
bool Place(int k);
void Backtrack(int k);
int n;
int sum;
vector<int> x;
public:
Queen(int m,int c,int b)
{
x.resize(m+1);
Re.resize(m+1);
n = c;
sum = b;
}
~Queen() { }
};
bool Queen::Place(int k)
{
for(int j=1;j<k;j++)
if(x[j]==x[k]) 不同男运动员和同一个女运动员配对
return false;
return true;
}
void Queen::Backtrack(int t)
{
if(t>n)
{
int temp=0; 第次还原为进行下次的累加
for(int i=1;i<=n;i++)
{
temp += (P[i][x[i]]) * (Q[x[i]][i]); 累加，得到一个可行解
}
if(sum<=temp) 记录最大可行解
{
sum=temp;
copy(x.begin(),x.end(),Re.begin());
}
}
else
for(int i=t;i<=n;i++)
{
swap(x[t],x[i]);
if(Place(t))
Backtrack(t+1);
swap(x[t],x[i]);
}
}
int PairUp(int n)
{
Queen X(n,n,0);
vector<int> p;
for(int i=0;i<=n;i++)
p.push_back(i);
copy(p.begin(),p.end(),X.x.begin());
X.Backtrack(1);
return X.sum;
}
int _tmain(int argc,_TCHAR* argv[])
{
ifstream fin("input.txt");
ofstream fout("output.txt");
int n,i,j,temp;
vector<int> r;
vector<int> t;
fin>>n;
r.push_back(0);
P.push_back(r);
t.push_back(0);
Q.push_back(t);
cout<<"从文件input.txt中获得数据...."<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
fin>>temp;
r.push_back(temp);
}
P.push_back(r);
for(vector<int>::iterator vr = r.begin()+1;vr != r.end();)
{
vr = r.erase(vr);
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
fin>>temp;
t.push_back(temp);
}
Q.push_back(t);
for(vector<int>::iterator vt = t.begin()+1;vt != t.end();)
{
vt = t.erase(vt);
}
}
cout<<"结果为："<<PairUp(n)<<"，并已保存至output.txt..."<<endl<<endl;
cout<<"男运动员"<<" & "<<"女运动员"<<endl;
for(i=1;i<=n;i++)
{
cout<<setw(4)<<i<<setw(12)<<Re[i]<<endl;
}
fout<<PairUp(n)<<endl;
return 0;
}
责任编辑：小草
