2023短学期0905场题解

yoongi blog / 2023-09-05 / 原文

1.挖地雷
Description
在一个地图上有N个地窖（N<=20），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。

当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

Input
N（表示地窖的个数）
W1 W2 W3 …… WN（表示每个地窖中埋藏的地雷数量）
A12…………… . A1N（地窖之间连接路径，其中Aij=1表示地窖i,j之间是否有通路：通Aij=1,不通Aij==0）
A23…………..A2N
…….. AN-1 N
Output
最多能挖多少地雷。

Samples
input
5
10 8 4 7 6
1 1 1 0
0 0 0
1 1
1
output
35

Solution

点击查看代码

#include <iostream>
using namespace std;

const int N = 20; 

int connect[N][N], mark[N], a[N], n;//mark用于标记该地窖是被访问过
int ans = 0;

void dfs(int now, int mine) {//mine表示当前挖到的地雷数量
    ans = max(ans, mine);
    for (int i = 1; i <= n; i++) {
        if (!mark[i] && connect[now][i]) {
            mark[i] = 1;
            dfs(i, mine + a[i]);
            mark[i] = 0;
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n - 1; i++) {
        for (int j = i + 1; j <= n; j++) {
            int x;
            cin >> x;
            connect[i][j] = x;
            connect[j][i] = x;
        }
    }
    for (int i = 1; i <= n; i++) {
        mark[i] = 1;
        dfs(i, a[i]);
        mark[i] = 0;
    }
    cout << ans << endl;
    return 0;
}****