运动员最佳匹配问题
3 10 2 3 2 3 4 3 4 5 2 2 2 3 5 3 4 5 1
52
1 #include <bits/stdc++.h> 2 using namespace std; 3 int n,Max,sum;//Max代表要求的 最大和,sum为临时求和 4 int data[22][22]; 5 int datax[22][22],datay[22][22]; 6 int book[22],maxSum[22]; 7 8 void dfs(int x){ 9 if(x>=n) {Max=max(Max,sum);return ;}// x到达n 之后,代表全部标记访问了 10 int cnt=0;//需要写 剪枝 函数,不然 超时,剪枝条件 就是 (之前x个一匹配好的sum和之后的x->n个最大值,加起来<=Max,减去) 11 for(int i=x;i<n;i++) cnt+=maxSum[i];// 求 x 之后 男生匹配 女生的最大值 和 12 if(sum+cnt<Max) return ;//若从第x组->第n组 当前搜索sum 加上 假设匹配后的最大值cnt,仍然小于Max ,可以剪枝了,Max为已经求得的最大值 13 for(int i=0;i<n;i++){ 14 if(!book[i]){ 15 book[i]=1; 16 sum+=data[x][i]; 17 dfs(x+1); 18 book[i]=0;//回溯 19 sum-=data[x][i]; 20 } 21 } 22 } 23 void input(int data[22][22]){ 24 for(int i=0;i<n;i++) 25 for(int j=0;j<n;j++) 26 cin>>data[i][j]; 27 } 28 int main() 29 { 30 cin>>n; 31 input(datax); 32 input(datay); 33 Max=0,sum=0; 34 for(int i=0;i<n;i++){ 35 for(int j=0;j<n;j++){ 36 data[i][j]=datax[i][j]*datay[j][i]; 37 maxSum[i]=max(maxSum[i],data[i][j]); 38 } 39 book[i]=0; 40 } 41 dfs(0); 42 cout<<Max<<endl; 43 return 0; 44 }优质内容筛选与推荐>>