题目描述

dfs，来了

实验小学邀请同学们参观实验小学内的各处美景，已知实验小学内共有n处景点。现在有n位该校的大队长承担导游。每个大队长对各个美景的熟悉程度是不同的，如何将n位大队长分配至n处景点，使得总的熟悉程度最大呢?

要求每个美景处都有一个大队长。

输入格式:
输入文件 visit.in 中有若干行:

第一行只有一个正整数n，表示有n个景点和n个大队长。

第二行至第 n+1 行共n行，每行有n个以空格分隔的正整数。第i+1行的第j个数

k(1≤k≤1000)，表示第i个大队长对景点i的熟悉程度为k。

输出格式:
输出文件 visit.out 只有一行，该行只有一个正整数，表示求得的熟悉程度之和最大值

【数据范围】
对于50%的数据，n<=9

对于100%的数据，n<=17

输入样例:
3
10 6 8
9 2 3
1 7 2
输出样例:
24

样例

3
10 6 8
9 2 3
1 7 2

24

算法

(dfs)

dfs搜素

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,a[20][20],b[20],cnt;
bool used[20];
void dfs(int step,int sum){
    if(step==n+1){
        cnt=max(cnt,sum);
        return;
    }
    if(cnt>sum+b[step]){
        return;
    }
    for(int i=1;i<=n;i++){
        if(!used[i]){
            used[i]=1;
            dfs(step+1,sum+a[step][i]);
            used[i]=0;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            b[i]=max(b[i],a[i][j]);
        }
    }
    for(int i=n;i>=1;i--)
        b[i]+=b[i+1];
    dfs(1,0);
    cout<<cnt;
}