|
#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; } |