题解 P2196 【挖地雷】

由于数据比较小，所以不用动归，用深搜，放心不会T的 题意有些不清楚，这其实是个有向图，只能从编号小的走到大的，但是起点是1~n都可以的 然后，极其暴力的代码，懒得多想 ```C++ #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; } ```