问题描述
有N个景点和N个导游，每个导游对每个景点熟悉程度不同，一个景点只需一个导游。求最大熟悉度。（0<=N<=17）
样例输入
4
1 2 3 4
4 3 2 1
2 3 4 1
2 4 3 1
样例输出
16
//本题算法是搜索，用深搜写，但是裸搜只有50分。
//下面就是智商高的看的剪枝了
//首先我们反向思维，将每个人对每个景点的熟悉度转换为不熟悉度（因为最多是1000，所以a[i,j]:=1000-a[i,j];即可）。
//至于用不熟练度去求是是为了能剪枝，因为如果只是比较熟悉度总和的最大值，过程中算出的当前值小于最大值并不能说明这个方案不能使用。但是比较不熟悉度总和的最小值时，在过程中当前值比现在的最小值大时就说明这种情况是不需要的（也就是说，这个情况搜下去，肯定没有我已得出的临时最优值大）。
//原标程中说用贪心求较优解，但是我仔细看了下，其实原标程中的z和min的初值其实就是1000*n。然后第一次搜索得到的值一定会将min更新，就会起到一个剪枝的作用。
#include<iostream>
using namespace std;
int n,now,minx;//n个导游,now为当前搜索得到的值,minx为最优值
int a[100][100],b[100];//a[i][j]表示第j个导游对第i个景点的熟悉度
//b[i]表示第i个景点是否以被分配
void go(int step){
if(step==n+1){
if(now<minx){
minx=now;
return;
}
}//如果分配完，尝试更新最优值
for(int i=1;i<=n;i++){
if(b[i]==0&&now+a[i][step]<minx){//i景点是否已被分配与剪枝
now+=a[i][step];
b[i]=1;//标记
go(step+1);//递归
now-=a[i][step];
b[i]=0;//回溯
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) b[i]=0;//初始化b数组
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>a[i][j];
a[i][j]=1000-a[i][j];
}//读入熟悉度，进行剪枝初始化
minx=1000*n;//初始化最优值
go(1);//深搜
cout<<n*1000-minx<<endl;//还原并输出；
return 0;
}
