题解 P2128 【赤壁之战】

lmrttx

2020-11-24 20:03:41

Solution

本题用 $DFS$ 解决。 先说下 $DFS$ 是什么吧。这就是搜索的一种,叫做深度优先搜索或者深搜。思想就是递归,判断何时退出搜索,以及回溯。回溯就是退回到某个过去的状态,重新开始搜索,这样更新答案的话答案正确性更高。 ------------ 接下来是更详细的介绍,如果已会自行跳过: 搜索是指对情况进行查找并且处理,如本题,我们就要把一艘艘船加进来处理。本题的处理是**通过情况更新最大值**。 这种搜索的思路是沿一个道路一直搜索,直到无路可走时,往回走,即回溯。我们由于有处理,所以可以从一个状态回到之前的状态。 图解,图片来源于百度。 ![](https://p1.ssl.qhimgs1.com/sdr/400__/t017ed8533be81d6521.jpg) ![](https://p3.ssl.qhimgs1.com/sdr/400__/t01d9b359c58b1c695d.png) 从1号点开始搜索,一直走到6号点,这时无路可走了。回溯。一直到2号点。接着搜索5号点,然后到7号点。分别搜索4号点和8号点与9号点那一条路径。此时又回溯到5号点了。退回至1号点。 由于走过的点会被标记为走过,所以此时所有点的标记都是走过。无路可走时,便退出搜索,输出答案。 这个标记数组通常叫做 $vis$ 或 $visit$ 。 本题就是 $DFS$ 的框架,回溯与搜索于代码中理解。 $DFS$ 本身是递归,请先了解递归。 ~~不用出门右转了,这边讲了。~~ 递归就是在一个函数中直接或间接地调用到函数本身。但是一直调用,总要有返回的时候。于是要设置边界,符合边界条件时,层层返回。这一过程用栈在计算机内部实现。栈是一种**先进后出**的数据结构,一个表。 介绍完毕,见题目吧。 --------------------------------------------------------- 题目分析: 发现是个搜索。看到 $"曹军战船之间由铁索相连,没有两艘战船在同一位置,也没有铁索两两相交或穿过战船。"$ 这句话时,就意识到是个点与点之间的 $DFS$ 了。搜索,判断是否返回,每次递归更新答案。 --------------------------------------------------------- 注释和细节等见代码,让我们用代码分析这种搜索吧! C++ CODE : ```cpp #include<bits/stdc++.h> using namespace std; #define MAX 1001 int n,m,a[MAX][MAX],answer,v[MAX],boat[MAX]; bool vis[MAX];//vis为标记数组,表示是否搜索过编号为多少的船 void dfs(int ans,int x){//ans为当前最优的战略价值,x为在这一次搜索中,已经有了几艘船。 answer=max(answer,ans);//更新答案 if(x>n)return;//退出边界 for(register int i=1;i<=n;i++){ if(vis[i]==0){//还未访问 bool tag=true;//标记,这个标记指从当前一艘船向别的船搜索,还有没有连接的船,还能不能搜索下去。如果不能,退出,返回上一层。 for(int j=1;j<=x;j++)//循环,搜索的基础。 if(a[boat[j]][i]==0)//如果两艘船没有连接 { tag=false;break; //无路可走,标记更新为假 } if(tag==true){ boat[x+1]=i; vis[i]=true; //每有一个新的搜索出发处,就要把这些东西处理一下。表示下一艘船是这艘,这艘被访问过了。 dfs(ans+v[i],x+1); //递归搜索,总价值加上当前的价值,船的数量加1. boat[x+1]=0; vis[i]=false; //回溯,回到搜索前的状态。 //因为我们的目标是让答案最优,所以回溯并不影响答案,只会让答案更加正确 } } } return; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>v[i]; for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; a[x][y]=666;//随便初始化为一个非0的数就可以了,因为为0时表示当前两艘船之间没有连接。 } //搜索策略,从每艘船出发搜一遍 for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis));//由于每次都重新搜一遍,所以要清零 memset(boat,0,sizeof(boat)); //boat表示在这一次搜索中,第几艘船的编号为多少 vis[i]=true; boat[1]=i;//初始化 dfs(v[i],1); } cout<<answer<<endl; return 0; } ``` 作为一个基本 $DFS$,这题的练习意义还是很大的。蒟蒻最近在练习写题解,如有不足,可私聊提出。谢谢阅读,真心希望这篇题解对您有帮助!