运动员最佳配对问题//Author:王子硕Date:2011/5/22//Description:#include<iostream>#include<fstream>#include<algorithm>#include<functional>#include<queue>usingnamespacestd;intn;int**P;int**Q;classArgNode{public:int*arg;//当前男运动员排列intt;//arg[1:t]已排列intval;//此种排列的竞赛优势值public:ArgNode(ArgNodeconst&source){arg=newint[n+1];for(inti=0;i<=n;++i){arg[i]=source.arg[i];}t=source.t;val=source.val;}ArgNode(int*arg,intt,intval){this->arg=newint[n+1];for(inti=0;i<=n;i++){this->arg[i]=arg[i];}this->t=t;this->val=val;};//大顶堆booloperator<(constArgNode&other)const{if(this->val>other.val){returnfalse;}elsereturntrue;}voidcompute();//计算当前节点值};voidArgNode::compute(){val=0;for(inti=1;i<=this->t;++i){val+=P[i][arg[i]]*Q[arg[i]][i];}}intAthletes(){//初始化priority_queue<ArgNode>Heap;int*iniArr=newint[n+1];inti,best=0;for(i=0;i<=n;++i){iniArr[i]=i;}ArgNode*initial=newArgNode(iniArr,0,0);deleteiniArr;Heap.push(*initial);while(!Heap.empty()){ArgNodefatherNode=Heap.top();Heap.pop();if(fatherNode.t==n)//是一个全排列，则比较节点内值是否比当前最优值更佳{if(best<fatherNode.val){best=fatherNode.val;}}else{for(i=fatherNode.t+1;i<=n;++i)//广度优先所搜子树{ArgNodenewNode(fatherNode);//把子节点内容先复制为父节点内容++newNode.t;//深度++newNode.arg[newNode.t]=fatherNode.arg[i];//选择第i个女选手newNode.arg[i]=fatherNode.arg[newNode.t];newNode.compute();//子节点计算valHeap.push(newNode);}}}returnbest;}intmain(){ifstreamin("input.txt");ofstreamout("output.txt");#defineincin#defineoutcoutintcases;in>>cases;for(intCase=1;Case<=cases;++Case){n;in>>n;inti,j;P=newint*[n+1];Q=newint*[n+1];for(i=0;i<=n;++i){P[i]=newint[n+1];Q[i]=newint[n+1];}for(i=1;i<=n;++i){for(j=1;j<=n;++j){in>>P[i][j];}}for(i=1;i<=n;++i){for(j=1;j<=n;++j){in>>Q[i][j];}}out<<"Case#"<<Case<<":"<<Athletes()<<endl;for(i=