题解 P2196 【挖地雷】

千反田 · 2019-04-09 16:40:11 · 题解

题解里一群大佬用图论 dp 记忆化 我都不会

本蒟蒻看了眼数据于是决定水一发爆搜

结果真的过了2333

我们用way数组表示两个地窖中是否存在联通路径

用trace数组表示该点是否遍历过

bool way[N][N],trace[N];

需要注意的是这里的路径是单向联通的

（感谢题解里@公主殿下MIKU的提醒 ）

每到一个地窖 判断是否后面是否还有路

int check(int x)
{
    for(int i=1;i<=n;++i)
    {
        if(way[x][i]&&!trace[i])
        return true;
    }
    return false;
}

大概的思想就是这样了

祭上代码

#include<bits/stdc++.h>
#define inf INT_MAX
#define N 25//个人习惯
using namespace std;
int number[N],ans=-inf,ansf[N],temp[N],n;
bool way[N][N],trace[N];
int check(int x)//判断函数
{
    for(int i=1;i<=n;++i)
    {
        if(way[x][i]&&!trace[i])//如果两个地窖联通且没有被遍历过
        return true;
    }
    return false;
}
void DFS(int now,int step,int num)
//now为现在处在的地窖编码，step为第几层，num为当前挖到的地雷数
{
    if(!check(now))//如果不可以再走了
    {
        if(ans<num)
        {
            ans=num;
            for(int i=1;i<=n;++i)
            {
                ansf[i]=temp[i];
            }
        }//更新答案
        return;
    }
    else//否则
    for(int i=1;i<=n;++i)
    {
        if(way[now][i]&&!trace[i])
        {
            trace[i]=true;
            temp[step]=i;
            DFS(i,step+1,num+number[i]);//快乐地继续爆搜
            trace[i]=false;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
     scanf("%d",&number[i]);
    for(int i=1;i<=n;++i)
     for(int j=i+1;j<=n;++j)
      scanf("%d",&way[i][j]);
    for(int i=1;i<=n;++i) //尝试从每一个地窖开始遍历
    {
        memset(temp,0,sizeof(temp));
        trace[i]=true; 
        temp[1]=i;
        memset(trace,false,sizeof(trace));
        DFS(i,2,number[i]);
    } 
    for(int i=1;i<=n;++i)
     printf("%d ",ansf[i]);
    printf("\n%d",ans);
    return ~~(0-0);//卖萌
}