挖地雷（洛谷）

大家好，欢迎来到IT知识分享网。

题目

原题

题目描述

在一个地图上有 $N(N\le 20)$
个地窖，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入格式

有若干行。

第 $1$ 行只有一个数字，表示地窖的个数 $N$。

第 $2$ 行有 $N$ 个数，分别表示每个地窖中的地雷个数。

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

第 $3$ 行有 $n-1$ 个数（$0$ 或 $1$），表示第一个地窖至第 $2$ 个、第 $3$ 个 $\dots$ 第 $n$
个地窖有否路径连接。如第 $3$ 行为 $11000\cdots 0$，则表示第 $1$ 个地窖至第 $2$ 个地窖有路径，至第 $3$
个地窖有路径，至第 $4$ 个地窖、第 $5$ 个 $\dots$ 第 $n$ 个地窖没有路径。

第 $4$ 行有 $n-2$ 个数，表示第二个地窖至第 $3$ 个、第 $4$ 个 $\dots$ 第 $n$ 个地窖有否路径连接。

……

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

输出格式

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

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

样例 #1

样例输入 #1

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

样例输出 #1

1 3 4 5 27

提示

【题目来源】

NOIP 1996 提高组第三题

思路

代码

下面这段代码是根据第一次写的dfs改的。可能有些变量啥的在记忆搜索里是不需要的。因为后面才发现后面的地窖无法通向前面的地窖

#include<iostream> using namespace std; bool flag[100][100]; //存储路径 //bool note[100]; //无用变量，记忆当前地窖是否经过，这里用的是记忆搜索该变量在本程序中不需要 int count[100]; //存储每个地窖的地雷数量 int ans[100],p[100],ss; //分别是最终路径，当前路径和最终路径中经过的地窖数 long int maxs=-1; //最多可以获取的地雷数量 int n; //总地窖数 void fun(int i,int sum,int steps){ 
    if(sum>maxs){ 
    //如果当前解可以获取的地雷数大于历史最大地雷数更新最大地雷数 maxs=sum; for(int i=0;i<steps;i++){ 
    //更新路径 ans[i]=p[i]; } ss=steps; //更新路劲长度 } for(int j=i+1;j<n;j++){ 
    if(flag[i][j]){ 
    p[steps]=j; fun(j,sum+count[j],steps+1); } } } int main(){ 
    cin>>n; for(int i=0;i<n;i++){ 
    cin>>count[i]; } for(int i=0;i<n-1;i++){ 
    //输入每个地窖的·地雷数 for(int j=i;j<n;j++){ 
    if(i==j){ 
    flag[i][j]=flag[j][i]=false; } else{ 
    cin>>flag[i][j]; flag[j][i]=flag[i][j]; } } } for(int i=0;i<n;i++){ 
    //将每个地窖作为初始地窖遍历 p[0]=i; //当前解路径经过的第一个地窖 fun(i,count[i],1); //dfs调用 } for(int i=0;i<ss;i++){ 
    //输出最优解的路径 cout<<ans[i]+1<<' '; } cout<<endl<<maxs; }