P2196

题目

题目描述：

在一个地图上有 N (N≤20)N\ (N \le 20) 个地窖，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后每次可以移动到一个编号比当前节点大且联通的节点去挖地雷，当无满足条件的节点时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入格式：

有若干行。

第 11 行只有一个数字，表示地窖的个数 NN。

第 22 行有 NN 个数，分别表示每个地窖中的地雷个数。

第 33 行至第 N+1N+1 行表示地窖之间的连接情况：

第 33 行有 n−1n-1 个数（00 或 11），表示第一个地窖至第 22 个、第 33 个 …\dots 第 nn 个地窖有否路径连接。如第 33 行为 1 1 0 0 0⋯01\space 1\space 0\space 0\space 0\cdots 0，则表示第 11 个地窖至第 22 个地窖有路径，至第 33 个地窖有路径，至第 44 个地窖、第 55 个 …\dots 第 nn 个地窖没有路径。

第 44 行有 n−2n-2 个数，表示第二个地窖至第 33 个、第 44 个 …\dots 第 nn 个地窖有否路径连接。

……

第 n+1n+1 行有 11 个数，表示第 n−1n-1 个地窖至第 nn 个地窖有否路径连接。（为 00 表示没有路径，为 11 表示有路径）。

输出格式：

第一行表示挖得最多地雷时的挖地雷的顺序，各地窖序号间以一个空格分隔，不得有多余的空格。

第二行只有一个数，表示能挖到的最多地雷数。

数据范围与说明：

【样例解释】

最优路径为 1→3→4→51 \to 3 \to 4 \to 5，结果为 2727。

【题目来源】

NOIP 1996 提高组第三题。

输入输出样例 #1

输入：

1
2
3
4
5
6
5
10 8 4 7 6
1 1 1 0
0 0 0
1 1
1

输出：

1
2
1 3 4 5
27

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
int n,ans,f[25][25],a[25],b[25];
vector<int> path,ans_path;
bool check(int x){
    for(int i=1;i<=n;i++){
        if(f[x][i]&&!b[i])  return false;
    }
    return true;
}
void dfs(int x,int sum){
    if(check(x)){
        if(ans<sum){
            ans=sum;
            ans_path=path;
        }
        return ;
    }
    for(int i=1;i<=n;i++){
        if(f[x][i]&&!b[i]){
            b[i]=1;
            path.push_back(i);
            dfs(i,sum+a[i]);
            path.pop_back();
            b[i]=0;
        }
    }
    return ;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            cin>>f[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        b[i]=1;
        path.clear();
        path.push_back(i);
        dfs(i,a[i]);
        b[i]=0;
    }
    for(int x:ans_path){
        cout<<x<<" ";
    }
    cout<<"\n";
    cout<<ans;
    return 0;
}