题解 P2196 【挖地雷】

2018-02-04 11:42:31


由于数据比较小,所以不用动归,用深搜,放心不会T的 题意有些不清楚,这其实是个有向图,只能从编号小的走到大的,但是起点是1~n都可以的 然后,极其暴力的代码,懒得多想

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,a[30],f[30][30],l[30],g[30],ans=0,cnt;
//a是存地雷数,f是存能否走通,l是深搜中临时记录1~n房间哪些走过,g是最终输出的数组
void dfs(int x,int sum)
{
    int flag=0;
    sum+=a[x];
    l[x]=1;
    for(int i=x+1;i<=n;i++)
        if(f[x][i]) flag=1,dfs(i,sum);//枚举下一个点
    if(!flag && sum>ans)
    {//如果没路可走就更新答案,并return
        ans=sum;
        cnt=0;
        for(int i=1;i<=n;i++)
            if(l[i]==1) g[++cnt]=i;
        return;
    }
    //回溯
    l[x]=0;
    sum-=a[x];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            scanf("%d",&f[i][j]);
    //以上输入
    for(int i=1;i<=n;i++)
        dfs(i,0);//枚举每个起点进行深搜
    for(int i=1;i<=cnt;i++)
        cout<<g[i]<<" ";
    cout<<endl<<ans;
    return 0;
}